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.