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 (∗): 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 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