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.

  • $\begingroup$ Probably not appropriate for this site. But, what theorems do you know about existence of perfecting matchings which could be applied? $\endgroup$ Commented Oct 14, 2012 at 18:14
  • $\begingroup$ 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. $\endgroup$ Commented Oct 14, 2012 at 19:59
  • 2
    $\begingroup$ What's inappropriate is that this looks like homework, and you have given us no reason that it is not. Voting to close. $\endgroup$
    – Igor Rivin
    Commented Oct 14, 2012 at 23:12
  • $\begingroup$ Also posted, without advising either site, to m.se: math.stackexchange.com/questions/213923/… --- voting to close. $\endgroup$ Commented Oct 15, 2012 at 4:20
  • $\begingroup$ R.R: The reason it looks like homework is not the question itself (mathematically, it's quite nice), but the lack of context. $\endgroup$ Commented Oct 15, 2012 at 7:27

1 Answer 1


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.

  • 4
    $\begingroup$ It's a nice argument, but answering homework problems is completely inappropriate. $\endgroup$
    – Igor Rivin
    Commented Oct 14, 2012 at 23:20
  • $\begingroup$ The argument works. The hypothesis gives a linearly independent subset of a vector space which dimension is m. Thanks $\endgroup$ Commented Oct 15, 2012 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.