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,. Sufficiency of : Let be an arbitrary graph with no perfect matching. We will find a bad set of vertices, 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 bad set in edge-maximal graph, then is also a bad set 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 bad set, 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. 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 vertex 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 . 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 and we obtain a matching in, a contradiction.
The Tutte–Berge formula says that the size of a maximum matching of a graph equals Tutte's condition is that, for every,. Equivalently, the expression inside the minimum is at least. Equivalently, the entire expression is at least. So, Tutte's condition holds iff the graph has a matching of size at least, iff the graph has a perfect matching.
