# Parity of Perfect Matchings

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.

Thanks!

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.

-
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

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