# Matching in bipartite graphs

Hi guys, I'm new here. Well, actually 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]$ a bipartite graph in which each vertex in X is of odd degree. Suppose at any two vertices of X have an even number of common neighbours. Show that G has matching covering every vertex of X.

• Probably not appropriate for this site. But, what theorems do you know about existence of perfecting matchings which could be applied? Commented Oct 14, 2012 at 18:14
• Hi. What isn't appropriate? I didn't understand... About the matchings, well, first of all X and Y couldn't have the same size what would imply to be impossible to find a perfect matching. ( I know it is an obvious comment but I made it to be sure that the problem it is clear) I thought it would be just a clever application of Hall's theorem... So, answering your question, I have hall's theorem. Commented Oct 14, 2012 at 19:59
• What's inappropriate is that this looks like homework, and you have given us no reason that it is not. Voting to close. Commented Oct 14, 2012 at 23:12
• Also posted, without advising either site, to m.se: math.stackexchange.com/questions/213923/… --- voting to close. Commented Oct 15, 2012 at 4:20
• R.R: The reason it looks like homework is not the question itself (mathematically, it's quite nice), but the lack of context. Commented Oct 15, 2012 at 7:27

Is it a homework problem? (If so, it is a nice one and new to me.) So you need to rule out the existence of a set $A \subseteq X$ such that the set $B$ of all $y \in Y$ adjacent to some $a \in A$ has strictly smaller size. Let $|B|=m$ and think of the neighbors of each $a \in A$ as a vector in $\mathbb{Z}_2^m.$ Each pair of these vecotrs is orthogonal in that their dot product is zero in $\mathbb{Z}_2.$ See what that tells you.