Tutte theorem

The set of Tutte (after William Thomas Tutte ) is a mathematical theorem from graph theory. It reads:

A graph G = (V, E) has exactly then a perfect matching if for every subset S of the vertex set V is the number of connected components of odd cardinality of GS at most equal to | S |, the number of nodes in S,.

GS denotes the graph that arises when one deletes the nodes of S and its incident edges from G. If we denote by q ( G ) denote the number of connected components with an odd number of nodes in a graph G = (V, E), this is how the second condition write briefly as | S | ≥ q ( GS ) for all subsets S of V.