Main Page | See live article | Alphabetical index 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. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.