# Matching in bipartite graphs

I'm studying graph theory and the follow question is driving me crazy. Any hint in any direction would be appreciated.

Here is the question:

Let $G = G[X, Y]$ be a bipartite graph in which each vertex in $X$ is of odd degree. Suppose that any two distinct vertices of $X$ have an even number of common neighbours. Show that $G$ has matching covering every vertex of $X$.

• Curiously, this is related to the "Clubs of Oddtown" problem. Every club in Oddtown has an odd number of members, and every two distinct clubs have an even number of members in common (your $X$ is the set of clubs, $Y$ the set of residents of Oddtown). The question usually asked is to show that there can't be more clubs than residents. It forms Chapter 3 of Matousek, Thirty-three Miniatures. The matching covering question doesn't come up, but still the discussion might be helpful. – Gerry Myerson Oct 14 '12 at 22:38
• Also posted, without advising either site, to MO: mathoverflow.net/questions/109633/matching-in-bipartite-graphs --- very bad form. – Gerry Myerson Oct 15 '12 at 4:19

Consider the adjacency matrix $M\in\Bbb F_2^{|X|\times|Y|}$ of the bipartite graph, i.e. M_{x,y}:=\left\{ \begin{align} 1 & \text{ if }x,y \text{ are adjacent} \\ 0 & \text{ else} \end{align} \right. then try to prove, it has rank $|X|$, and then, I think, using Gaussian elimination (perhaps only on the selected linearly independent columns) would produce a proper matching..
Let $A$ be the adjacency matrix of $G$, with rows indexed by $X$ and columns by $Y$. The material in the references (specifically, the analysis of the Oddtown problem) shows that the rows of $A$ are linearly independent as vectors in $\Bbb F_2^{|Y|}$, so the rank of $A$ is $|X|$. $A$ therefore contains an $|X|\times|X|$ invertible submatrix $B$. I’ve not entirely thought through the details, but I’d try to show that this submatrix must contain a permutation matrix, which will give you the desired matching. It may be useful to row-reduce $B$; note that this is exceptionally simple over $\Bbb F_2$.
Added: Just look at the determinant of $B$ as defined by the Leibniz formula: one of the terms must be non-zero.
• Very nice! ${}$ – joriki Oct 15 '12 at 1:45