# Prove that the number of "good" subsets in $A$ and the number of "good" subsets in $B$ have the same parity.

Let $$G=(A,B)$$ be a bipartite graph. We call a subset $$X$$ of $$A$$ "good" if every vertex of $$B$$ is adjacent to at least one vertex of $$X$$. We call a subset $$Y$$ of $$B$$ "good" if every vertex of $$A$$ is adjacent to at least $$1$$ vertex in $$Y$$. Prove that the number of "good" subsets in $$A$$ and the number of "good" subsets in $$B$$ have the same parity.

My idea is to "simplify" the $$G$$ graph but keep the parity of $$|X|$$ and $$|Y|$$ . But I am stuck with how to transform my graph G . I hope to get help from everyone. Thanks very much!

• @Arthur Yes, sorry I'm not good at English. I will fix it right away! Commented Nov 21, 2022 at 8:48
• What is a two-sided graph? Could we be talking about a bipartite graph? Commented Nov 21, 2022 at 12:37
• @kabenyuk Yes, sorry because I'm not good at English. I will fix it right away Commented Nov 21, 2022 at 12:42

Here's an answer involving strong induction where we "add" vertices to either set. The base case, where $$|A| = |B| = 0$$, is obvious. Now, assume that the parity of $$|X|$$ and $$|Y|$$ are equal for any graph $$G$$ satisfying $$|A| \leq a$$ and $$|B| \leq b$$.

Now, consider any new graph $$G'$$ satisfying $$|A| = a+1$$ and $$|B| = b$$. Denote one vertex of $$A$$ to be $$v$$, and let the neighbors of $$v$$ be the set of vertices $$B_v$$. Furthermore, denote $$A'$$ to be $$A \setminus \{v\}$$ (i.e., all vertices of $$A$$ except for $$v$$), and denote $$B'$$ to be $$B \setminus A_v$$ (all vertices in $$B$$ not neighboring $$v$$).

Finally, Let $$X_{G,H}$$ to be the subsets of $$G$$ (a subset of the vertices of $$A$$) that are adjacent to all vertices in $$H$$ (a subset of the vertices of $$B$$), and define $$Y_{G,H}$$ similarly. Note that $$X_{A,B} = X$$.

Claim. $$|X| = |X_{A',B}| + |X_{A', B'}|$$.

Proof. Every set of vertices in $$X$$ either includes $$v$$ or does not include $$v$$. If $$v$$ is not included, then clearly there are $$|X_{A',B}|$$ ways to finish (as we have simply "removed" $$v$$ from the graph). If $$v$$ is included, then all vertices in $$A_v$$ neighbor $$v$$ already, so the rest only have to neighbor the vertices not in $$A_v$$, namely $$A'$$.

Claim. $$|Y| = |Y_{A',B}| - |Y_{A',B'}|$$.

Proof. Clearly, every set in $$Y$$ must also be in $$|Y_{A',B}|$$ (as we need sets in $$Y$$ to border every vertex in $$A'$$). However, we also require these sets to border $$v$$. Thus, they must include a vertex in $$A_v$$; the ones that fail, therefore, are the ones that include no vertices in $$A_v$$, i.e., sets in $$Y_{A',B'}$$.

Now, to finish, note that by our induction hypothesis $$|X_{A',B}| \equiv |Y_{A',B}| \pmod{2}$$, and $$|X_{A',B'}| \equiv |Y_{A',B'}| \pmod{2}$$. Therefore, $$|X| - |Y| \equiv |X_{A',B}| + |X_{A', B'}| - \left(|Y_{A',B}| - |Y_{A',B'}|\right) \equiv |X_{A', B'}| + |Y_{A',B'}| \equiv 0 \pmod{2}$$ as expected.

A similar proof applies when $$|A| = a$$ and $$|B| = b+1$$; strong induction finishes.

Disclaimer: This is not an answer from a reputable source.

For each $$b \in B$$, let $$\mathcal{A}_b$$ be the family of subsets of $$A$$ that does not contain any neighbor of $$b$$. Then by the principle of inclusion-exclusion, the number of good $$X$$ is given by $$\# \text{good } X = \sum_{S \subset B} (-1)^{\#{S}}\lvert{ \bigcap_{b \in S} \mathcal{A}_b \rvert}.$$ Now note that $$\lvert{ \bigcap_{b \in S} \mathcal{A}_b \rvert}$$ is $$2^{t(S)}$$, where $$t(S)$$ is the number of vertices in $$X$$ not adjacent to any $$b \in B$$. It is odd iff $$t(S) = 0$$. Thus we have $$\# \text{good } X \equiv \sum_{S \subset B, t(S) = 0} 1 \bmod{2}.$$ The RHS is precisely the number of good $$Y$$.

Alternatively, one can use the third proof listed here

• What is "#" ? Can you tell more about the application of the principal of inclusion-exclusion in this problem? I have read about the principal of inclusion-exclusion , but I do not understand your application in this problem . Specifically the 4th line. Thanks very much Commented Nov 23, 2022 at 18:00
• $\#$ denotes the number of elements in a set. Commented Nov 23, 2022 at 18:01
• So why can $#X$ be calculated like that? Can you say clearer ? Commented Nov 23, 2022 at 18:02
• The principle of inclusion-exclusion states(see en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle formal generalization) states that the number of elements of $2^{A}$ not contained in any of the $\mathcal{A}_b$ is given by the formula on the 4-th line. Commented Nov 23, 2022 at 18:04
• I think in the $4$th line it should be $b \in S$ ? Commented Nov 23, 2022 at 18:13