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?

  • $\begingroup$ 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 ? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ llya Bogdanov:It is a very nice proof! Thank you very much! $\endgroup$ – user173856 Nov 13 '15 at 2:48
  • $\begingroup$ Hello, llya Bogdanov. Thank you very much for your help. Your proof is so ingenious. I have never seen this kind of method before. Would you please tell me how you got the idea of the proof above? By the way, do you know any result relative to my question? $\endgroup$ – user173856 Nov 13 '15 at 14:56

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$).

| cite | improve this answer | |
  • $\begingroup$ I'm confused: doesn't $|S|=2$ here, since it contains the pairs $(u,x)$ and $(v,y)$? $\endgroup$ – gowers Nov 11 '15 at 23:34
  • $\begingroup$ Yes, here $|S|=2$, the example above is not a counterexample! $\endgroup$ – user173856 Nov 12 '15 at 5:24
  • $\begingroup$ I see, sorry about that, I thought you meant for $S$ to be a subset of edges. $\endgroup$ – Katie Edwards Nov 12 '15 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.