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 aProof
First we write the condition: : where denotes the number of odd components of the subgraph induced by . Necessity of (∗): 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), ., pp. 76–78. Sufficiency of (∗): Let be an arbitrary graph with no perfect matching. We will find a ''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 are 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 isEquivalence to the Tutte-Berge formula
TheIn 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
*External links
* Sunil ChandranNotes
References
* * {{Cite book , last1=Lovász , first1=László , author1-link=László Lovász , last2=Plummer , first2=M. D. , author2-link=Michael D. Plummer , title=Matching theory , year=1986 , publisher=North-Holland , location=Amsterdam , isbn=0-444-87916-1 Matching (graph theory) Theorems in graph theory Articles containing proofs