Lesson 6

Theorem (Tutte, 1947). There exists a perfect matching in \(G\) if and only if the determinant of the Tutte matrix is not the zero polynomial.

The theorem follows from the next two lemmas.

Lemma. If \(G\) has a perfect matching, then \(\det(T) \neq 0\).

Proof. Without loss of generality, suppose \(\{(1, 2), (3, 4), \dotsc, (n-1, n)\}\) is a perfect matching.

Consider the permutation \(\sigma_{M} = (1, 2)(3, 4) \dotsc (n-1, n)\). Let us examine the term in the determinant expansion that corresponds to \(\sigma_{M}\). We aim to show that this term cannot be cancelled, implying that the determinant is non-zero.

\[\begin{align*}\prod_{i=1}^{n}T_{i, \sigma_M(i)}&= x_{1,2}\cdot (-x_{1,2}) \cdot x_{3,4}\cdot (-x_{3,4}) \cdot … \cdot x_{n-1,n}\cdot (-x_{n-1,n}) \\&= (-1)^{n/2}(x_{1,2})^{2} \cdot (x_{3,4})^{2} \cdots (x_{n-1,n})^{2}.\end{align*}\]

Since each variable appears squared, there exists only one permutation that contributes this specific product of variables. Therefore, no other permutation can cancel this term, and it follows that \(\det(T) \neq 0\).◼