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. It 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: