is not in , therefore the second vertex is -matched by a different edge and we continue in this manner. Let denote the last vertex of . If the last edge of is in , then has to be , since otherwise we could continue with an edge from (even to arrive at or ). In this case we define . If the last edge of is in , then surely } for analogous reason and we define . Now is a cycle in of even length with every other edge in . We can now define (where is symmetric difference) and we obtain a matching in , a contradiction. Equivalence to the Tutte-Berge formula The Tutte–Berge formula says that the size of a maximum matching of a graph equals . Equivalently, the number of unmatched vertices in a maximum matching equals . This formula follows from Tutte's theorem, together with the observation that has a matching of size if and only if the graph obtained by adding new vertices, each joined to every original vertex of , has a perfect matching. Since any set which separates into more than components must contain all the new vertices, (*) is satisfied for if and only if . In infinite graphs For connected infinite graphs that are locally finite (every vertex has finite degree), a generalization of Tutte's condition holds: such graphs have perfect matchings if and only if there is no finite subset, the removal of which creates a number of finite odd components larger than the size of the subset. See also Bipartite matching Hall's marriage theorem Petersen's theorem External links Sunil Chandran, Tutte's theorem on existence of a perfect matching (in YouTube). Derive Hall's theorem from Tutte's theorem (in Math StackExchange). Notes References Matching (graph theory) Theorems in graph theory Articles containing proofs