In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of finite 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 Our goal is to characterize all graphs that do not have a perfect matching. Let us 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