Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Probably not appropriate for this site. But, what theorems do you know about existence of perfecting matchings which could be applied? –  Aaron Meyerowitz Oct 14 '12 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. –  Rodrigo Ribeiro Oct 14 '12 at 19:59
2  
What's inappropriate is that this looks like homework, and you have given us no reason that it is not. Voting to close. –  Igor Rivin Oct 14 '12 at 23:12
    
Also posted, without advising either site, to m.se: math.stackexchange.com/questions/213923/… --- voting to close. –  Gerry Myerson Oct 15 '12 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. –  Johan Wästlund Oct 15 '12 at 7:27
show 1 more comment

1 Answer

up vote 1 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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