# A question about a specific partition of a graph

Let $G=(V,E)$ be a graph and $V=A\cup B$ satisfying

$(1)A\cap B=\emptyset;$

$(2)|N_G(v)\cap B|\geq |N_G(v)\cap A|,\forall v\in A$ and $|N_G(v)\cap A|\geq |N_G(v)\cap B|,\forall v\in B$.

Let $S=\{(u,v)|u\in A,v\in B,N_G(u)\cap N_G(v)\neq \emptyset\}$ and $G[A],G[B]$ be the induced subgraphs of $G$ by $A$ and $B$ respectively.

I conjecture that $|S|\geq |E(G[A])|+|E(G[B])|$, is that right?

• Have you any thoughts (towards a prove) to share on this ? In what context does this question appear to you ? Which references did you already check for a proof of the conjecture ? Have you checked, if somebody else conjectured the same/something similar ? – Johannes Trost Nov 12 '15 at 11:42

Denote $d_A(v)=|N_G(v)\cap A|$, $d_B(v)=|N_G(v)\cap B|$. Set $S_A=\{(a,b)\in A\times B\colon N_G(a)\cap N_G(b)\cap A\neq\varnothing\}$ and $S_B=\{(a,b)\in A\times B\colon N_G(a)\cap N_G(b)\cap B\neq\varnothing\}$. Clearly, $S_A,S_B\subseteq S$. Now we claim that $|S_A|\geq 2|E(G[A])|$ and, similarly, $|S_B|\geq 2|E(G[B])|$; this yields the required inequality.
To prove the first inequality, consider any edge $e=(a_1,a_2)$ with $a_1,a_2\in A$; denote $d_i=d_B(a_i)$ and notice that $d_i\geq d_A(a_i)\geq 1$. For each neighbor $b_1\in B$ of $a_1$ (there are $d_1$ such), we say that $e$ contribures $1/d_2$ to the pair $(a_2,b_1)\in S_A$. Similarly, for every neighbor $b_2$ of $a_2$ (there are $d_2$ such), the edge $e$ contributes $1/d_1$ to the pair $(a_1,b_2)\in S_A$. Thus, the total contrivution of $e$ is $d_1/d_2+d_2/d_1\geq 2$, and the total contribution of all edges is $\geq 2|E(G[A])|$. On the other hand, the total contribution to any pair $(a,b)\in S_A$ is at most $d_A(a)/d_B(a)\leq 1$. Hence, the total contribution of all edges is at most $|S_A|$. Therefore, $|S_A|\geq 2|E(G[A])|$, as required.
I think this is false. Let $G$ be a cycle on 4 vertices with edges $uv,vx,xy,uy$ and set $A = \{u,v\}$ and $B = \{x,y\}$. Then $|E(G[A])| = |E(G[B])| = 1$ but $|S| = 0$ since $u$ and $y$ have no common neighbours (and neither do $v$ and $x$).
• I'm confused: doesn't $|S|=2$ here, since it contains the pairs $(u,x)$ and $(v,y)$? – gowers Nov 11 '15 at 23:34
• Yes, here $|S|=2$, the example above is not a counterexample！ – user173856 Nov 12 '15 at 5:24
• I see, sorry about that, I thought you meant for $S$ to be a subset of edges. – Katie Edwards Nov 12 '15 at 7:33