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!
 A: 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.
A: 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
