8
$\begingroup$

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.

  • 0
    Yes, that's right. No, I have no idea what's going on here combinatorially.2011-01-04

1 Answers 1

2

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.

  • 1
    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.2011-11-08