2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\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
    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$
    – Rodrigo Ribeiro
    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$
    – Gerry Myerson
    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$
    – Johan Wästlund
    Commented Oct 15, 2012 at 7:27

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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$
    – Rodrigo Ribeiro
    Commented Oct 15, 2012 at 22:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .