Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Source: Lovasz, Plummer - Matching Theory

I had a question related to the number of perfect matchings in a graph. While going through the 8th Chapter on Determinant and Matchings in the text I stumbled across the first exercise problem. So far, I have been unable to solve either of the directions stated in the problem which I present below.

A graph $G$ has an even number of perfect matchings if and only if $\exists S \subseteq V(G); (S \neq \phi)$ such that all vertices in $V(G)$ are adjacent to an even number of vertices in $S$.

At the moment, all I can see is just that finding determinant of $A(G)$ over $F_2$ reveals the parity of perfect matchings. But, owing to my limited Linear Algebra background, I cannot see anything beyond. I would be real glad if someone can help me with this query.


EDIT The purpose of the current bounty is to get a combinatorial answer to the question if possible. I will remove this note after

(i) there is a combinatorial answer, or
(ii) the bounty period expires

whichever comes first.

share|cite|improve this question
Considering $A(G)$ as a matrix over $F_2$, $A(G)$ has determinant 0 iff it has nontrivial kernel. Nonzero vectors in the kernel correspond exactly to sets $S$ of vertices with the property you want. – Chris Eagle Jan 4 '11 at 21:54
I see, thats cool. Let me make sure that I understand you. If A is singular over $F_2$ (meaning number of PMs is even) then all non-zero vectors $x$ for which $A.x = 0$ give one such $S$ (That, the vertex $v_i$ hits an even number of guys in $S$ follows from $Ax$ being $0$). (You are thinking of these vectors as indicator for the set $S$ of vertices). Thats very, very neat (at least for me its very neat). Let me know if I understood you. Finally, one last question. Could you also give some combinatorial arguments? Thanks for your time. – Akash Kumar Jan 4 '11 at 22:27
Yes, that's right. No, I have no idea what's going on here combinatorially. – Chris Eagle Jan 4 '11 at 22:55
up vote 2 down vote accepted

The answer can be found by regarding an element in the kernel of the adjacency matrix over $F_2$, see the comments.

Note also that although the determinant of the adjacency matrix modulo 2 gives the parity of the number of matchings, it is not at all true that the determinant of the adjacency matrix can often be used to determine the number of matchings.

share|cite|improve this answer
sorry for the super late response. I just wanted to ask if I should mark this answer as accepted. I know the answer is correct, but Chris already answered it in the comments. Is there some trend that I should follow on what to do in these cases? Let me know. Thanks again – Akash Kumar Nov 8 '11 at 17:46
@AkashKumar I don't know about a trend, but I wanted to look through the unanswered combinatorics questions and found many that were actually answered in the comments, so I answered a lot of them (and upvoted answered on "unanswered" questions with a zero-vote answer). I do think that it is worthwhile if answered question are visibly answered. This is basically achieved by the single upvote, so the checkmark by you is not necessary. It expresses primarily your own satisfaction. Note that I marked it CW as well. I actually think that you should have written and accepted the answer. – Phira Nov 8 '11 at 18:32
@AkashKumar I am quite disappointed that the question alert starting with "sorry for the super late response" was not an answer to the bounty running out within the hour. – Phira Nov 8 '11 at 18:33
I am very sorry. I actually check my math stack exchange account at very large gaps of time :( Sorry for disappointing you. I am accepting your answer. Again, I apologize for making a comment this late when the bounty period was about to run out. – Akash Kumar Nov 8 '11 at 18:43

Your Answer


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.