Tutte 1947: G has a perfect matching iff for every vertex subset S, the number of odd components of G − S is at most |S|. Generalises Hall (bipartite) to arbitrary graphs. Berge's formula quantifies the maximum matching size.
Tutte 1947: G has a perfect matching iff for every vertex subset S, the number of odd components of G − S is at most |S|. Generalises Hall (bipartite) to arbitrary graphs. Berge's formula quantifies the maximum matching size.