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$ – Aaron Meyerowitz Oct 14 '12 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$ – Rodrigo Ribeiro Oct 14 '12 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 Oct 14 '12 at 23:12
  • $\begingroup$ Also posted, without advising either site, to m.se: math.stackexchange.com/questions/213923/… --- voting to close. $\endgroup$ – Gerry Myerson Oct 15 '12 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$ – Johan Wästlund Oct 15 '12 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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