Sufficient conditions for matchings
Ian Muir Anderson · Proceedings of the Edinburgh Mathematical Society · 1972
A graph G is said to possess a perfect matching if there is a subgraph of G consisting of disjoint edges which together cover all the vertices of G. Clearly G must then have an even number of vertices. A necessary and sufficient condition for G to possess a perfect matching was obtained by Tutte (3). If S is any set of vertices of G, let p(S) denote the number of components of the graph G – S with an odd number of vertices. Then the condition is both necessary and sufficient for the existence of a perfect matching. A simple proof of this result is given in (1).