Tutte theorem
In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected 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. Intuition 

The goal is to characterize all graphs that do not have a perfect matching. Start with the most obvious case of a graph without a perfect matching: a graph with an odd number of vertices. In such a graph, any matching leaves at least one unmatched vertex, so it cannot be perfect. A slightly more general case is a disconnected graph in which one or more components have an odd number of vertices (even if the total number of vertices is even). Let us call such components odd components. In any matching, each vertex can only be matched to vertices in the same component. Therefore, any matching leaves at least one unmatched vertex in every odd component, so it cannot be perfect. Next, consider a graph G with a vertex u such that, if we remove from G the vertex u and its adjacent edges, the remaining graph (denoted ) has two or more odd components. As above, any matching leaves, in every odd component, at least one vertex that is unmatched to other vertices in the same component. Such a vertex can only be matched to u. But since there are two or more unmatched vertices, and only one of them can be matched to u, at least one other vertex remains unmatched, so the matching is not perfect. Finally, consider a graph G with a set of vertices  such that, if we remove from G the vertices in  and all edges adjacent to them, the remaining graph (denoted ) has more than  odd components. As explained above, any matching leaves at least one unmatched vertex in every odd component, and these can be matched only to vertices of  - but there are not enough vertices on  for all these unmatched vertices, so the matching is not perfect. We have arrived at a necessary condition: if G has a perfect matching, then for every vertex subset  in G, the graph  has at most  odd components. Tutte's theorem says that this condition is both necessary and sufficient for the existence of perfect matching. Tutte's theorem 
A graph, , has a perfect matching if and only if for every subset  of , the subgraph  has at most  odd components (connected components having an odd number of vertices). Proof

First we write the condition:

where  denotes the number of odd components of the subgraph induced by . Necessity of (∗): This direction was already discussed in the section Intuition below, but let us sum up here the proof. Consider a graph , with a perfect matching. Let  be an arbitrary subset of . Delete . Let  be an arbitrary odd component in . Since  had a perfect matching, at least one vertex in  must be matched to a vertex in . Hence, each odd component has at least one vertex matched with a vertex in . Since each vertex in  can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), . Sufficiency of (∗): Let  be an arbitrary graph with no perfect matching. We will find a so-called Tutte violator, that is, a subset  of  such that . We can suppose that  is edge-maximal, i.e.,  has a perfect matching for every edge  not present in  already. Indeed, if we find a Tutte violator  in edge-maximal graph , then  is also a Tutte violator in every spanning subgraph of , as every odd component of  will be split into possibly more components at least one of which will again be odd. We define  to be the set of vertices with degree . First we consider the case where all components of  are complete graphs. Then  has to be a Tutte violator, since if , then we could find a perfect matching by matching one vertex from every odd component with a vertex from  and pairing up all other vertices (this will work unless  is odd, but then  is a Tutte violator). Now suppose that  is a component of  and  are vertices such that . Let  be the first vertices on a shortest -path in . This ensures that  and . Since , there exists a vertex  such that . From the edge-maximality of , we define  as a perfect matching in  and  as a perfect matching in . Observe that surely  and . Let  be the maximal path in  that starts from  with an edge from  and whose edges alternate between  and . How can  end? Unless we arrive at 'special' vertex such as  or , we can always continue:  is -matched by , so the first edge of  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 perfect 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

Notes

References
 
 

Matching (graph theory)
Theorems in graph theory
Articles containing proofs