2
$\begingroup$

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?

$\endgroup$
1
  • $\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$ Nov 12, 2015 at 11:42

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ llya Bogdanov:It is a very nice proof! Thank you very much! $\endgroup$
    – user173856
    Nov 13, 2015 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, 2015 at 14:56
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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