Answers are grounded in this paper and cite their sources.
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 ).
No takes yet. Share an insight, caveat, or question.
Ian Anderson (1972) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: