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?



A question about a specific partition of a graph
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.


