Bipartite Graphs-Neighborhood Size

Question

A bipartite graph $G(U,V)$ with two vertex partitions $U$ and $V$, and two subsets of $U$, $U_1$ and $U_2$, prove $$|N(U_1)|+|N(U_2)|≥|N(U_1∪U_2)|+|N(U_1∩U_2)|$$

I can only prove equal. How to prove greater than?

Answer 1

Wait, hang on.

I can only prove equal. How to prove greater than?

If someone asks you to prove $A \ge B$, and you managed to prove $A = B$, you're done! You proved more than was asked of you, not less. You don't need to also "prove greater than". If they are equal, they are equal.

What you should be worried about when that happens is, why were you asked to only prove $A \ge B$ when in fact $A = B$? Either whoever asked you the question was satisfied with you proving just the weaker statement for some reason, or your proof is incorrect.

In this case, I'm afraid your proof is incorrect.

Take the bipartite graph on $V = \{1,2\} \cup \{a,b\}$ with edges $\{1,a\},\{1,b\},\{2,b\}$ and let $U_1 = \{1\}$ and $U_2=\{2\}$. You have $|N(U_1)|=2,|N(U_2)|=1,|N(U_1 \cup U_2)|=2$ and $|N(U_1 \cap U_2)|=0$. So $2+1 \ge 2+0$ holds as an inequality, not an equality.

Go over your proof-of-equality carefully, and see where the error is. In all likelihood your argument will let you show the inequality.

Answer 2

Consider four set of vertices from $V$, defined as follows:

• $V_1 = N(U_1 \cap U_2)$, vertices connected to the vertices common to $U_1$ and $U_2$
• $V_2 = (N(U_1)\cap N(U_2))\backslash V_1$, the vertices other than $V_1$ connected to both $U_1$ and $U_2$
• $V_3 = N(U_1)\backslash (V_1\cup V_2)$, vertices connected to $U_1$ but not $U_2$
• $V_4 = N(U_2)\backslash (V_1\cup V_2)$, vertices connected to $U_2$ but not $U_1$

Then

• $|N(U_1)|=|V_1|+|V_2|+|V_3|,$
• $|N(U_2)|=|V_1|+|V_2|+|V_4|,$
• $|N(U_1\cup U_2)|=|V_1|+|V_2|+|V_3|+|V_4|,$ and
• $|N(U_1\cap U_2)|=|V_1|$

and the inequality follows, of size $|V_2|$.