Perfect matching
A perfect matching for a connected graph is a matching, or subset of edges without common vertices, which touch all vertices exactly once. A graph with an odd
number of vertices is allowed one unmatched vertex.
Note: Since a complete undirected, connected graph without self-loops has n(n-1)/2 edges, where n is the number of vertices, a perfect match consists of
n/2 edges. The name of the term comes from matching each vertex with exactly one other vertex.
Referenced By
List of combinatorics topics | List of mathematical topics (P-R)
|
