Let be any finite graph. has a complete matching if and only if for all the inequality holds, where is the number of the components of the graph with odd number of vertices. This is called the Tutte condition.
The sufficiency is proved in a few steps indirectly.
It is very easy to see that if is even, then and . This will be used later. And if the Tutte condition holds, applying it to gives is even.
If is an even component in , then adding its vertex to gives , because it creates at least one odd component. But this with the Tutte condition gives , which contradicts the maximality of . So there are no even components in .
Let be an odd component of , and let any of its vertices. Assume there is no complete matching in . Since is minimal counterexample, there exits a set such that , but because of it is at least . Then , which contradicts the maximality of . So by removing any vertex from an odd component the remaining part has a complete matching.
Represent each odd components by one vertex, and remove the edges in . From the definition of this is a bipartite graph. If we choose vertices from the representatives of the odd components, they are together adjacent to at least vertices in , otherwise we could remove less than vertices from thus from , and still get odd component, which violates the Tutte condition. So there is complete matching in this reduced graph because of Hall’s marriage theorem.
The complete matching in the reduced graph covers and exactly one vertex in each odd component. But there is also a matching in the rest of each odd component covering the rest as proven in , and from there are no even components. Combining these gives a complete matching of , which is a contradiction.