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 an 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 of the edges. The name of the term comes from matching each vertex with exactly one other vertex.