Matchings · Tutte's Theorem and Berge's Formula (Optional)

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Suppose that \(G\) has a perfect matching \(M\). Let us remove some set of vertices \(S \subseteq V(G)\) from the graph. Consider an odd component \(C\) of \(G-S\). Inside \(C\), the matching \(M\) cannot cover all vertices by edges lying completely in \(C\), because \(|C|\) is odd. Therefore, at least one vertex of \(C\) must be matched by an edge going to \(S\).

Moreover, different odd components of \(G-S\) need different vertices of \(S\). Thus every perfect matching gives the inequality \[o(G-S) \le |S| \ .\]

If for some \(S\) we have \(o(G-S)>|S|\), then this is a certificate that no perfect matching exists. The remarkable theorem of Tutte says that these are the only certificates.

For the curious 🤓

During World War II, Tutte worked at Bletchley Park. One of his famous contributions was to the attack on the Lorenz cipher, used for high-level German military communications. From intercepted messages, and without seeing the machine itself, Tutte reconstructed the structure of the cipher machine.

In mathematics, Tutte was one of the people who shaped modern graph theory: besides the matching theorem below, his work includes deep results on connectivity, important contributions to matroid theory, and the Tutte polynomial, which contains the chromatic polynomial and several other graph invariants as special cases.