Bondy, Murty Graph Theory exercise 16.2.12 (by Noga Alon)

Question

Let $G = (U\sqcup V, E)$ be a bipartite graph in which each vertex of $U$ is of odd degree. Suppose that any two vertices of $U$ have an even number of common neighbours. Show that $G$ has a matching covering every vertex of $U$.

Let $S=\{u_1,\ldots,u_t\}\subseteq U$. We must show that $|N(S)|\ge |S|=t$, where $N(S)$ is the set of neighbors of $S$. In order to use the information about common neighbors, I thought it would be useful to use inclusion-exclusion. We have $$\begin{align} |N(S)| &= \left| \bigcup_{i=1}^t N(u_i) \right| \\&= \sum_{i=1}^t |N(u_i)|-\sum_{1\le i<j\le t} |N(u_i)\cap N(u_j)|+\cdots \\&+ (-1)^{t+1} |N(u_1)\cap N(u_2)\cap\ldots \cap N(u_t)| \end{align}$$

We first sum over odd numbers; the second one sums over even numbers. But I don't really see how to continue.

Answer 1

Let $N(S) = \{v_1, \dots, v_n\}$. For each $u_i$ we can create a binary vector $z_i$ with $n$ entries, with the $j$-th entry being $1$ if and only if $v_j$ is a neighbor of $u_i$. It's easy to see that when viewed as vectors over the vector space $\mathbb{Z}_2^n$ the $z_i$'s are linearly independent. So $$|S| = t = \dim \text{span}\{z_i, i\in[t]\} \leq \dim \mathbb{Z}_2^n = n = |N(S)|$$ and the result follows from Hall's marriage theorem.

Proof of linear independence:

• For $i\neq j$, the inner product $z_i \cdot z_j$ is equal to the number of common neighbours of $u_i$ and $u_j$ modulo $2$ so by hypothesis it is equal to $0$
• The inner product $z_i \cdot z_i$ is equal to the degree of $u_i$ modulo $2$ which, again by hypothesis, is equal to $1$

The above two facts are enough to show that $z_i$'s are linearly independent.