Tutte theorem

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs and is a special case of the Tutte–Berge formula.

A graph, $G = (V, E)$ , has a perfect matching if and only if for every subset $U$ of $V$ , the subgraph induced by $V - U$ has at most $| U |$ connected components with an odd number of vertices.

First we write the condition:

where $o(X)$ $o(X)$ denotes the number of odd components of the subgraph induced by $X$ $X$ .