Lesson 6

Tutte's theorem answers the question: does a perfect matching exist? But it also suggests what to do when the answer is no.

If \(o(G-S)>|S|\), then the odd components of \(G-S\) are competing for too few vertices of \(S\). At least \[o(G-S)-|S|\] vertices must remain uncovered by any matching.

This motivates the following definition. The deficit of a graph \(G\) is the number of vertices left uncovered by a maximum matching: \[\operatorname{def}(G)=|V(G)|-2\alpha'(G) \ .\] In particular, \(\operatorname{def}(G)=0\) if and only if \(G\) has a perfect matching.

Claude Berge proved a generalization of Tutte's theorem. Instead of only telling us when the deficit is zero, it gives the deficit exactly: the same kind of odd-component obstruction measures how far the graph is from having a perfect matching.