Near-perfect matching

The term near-perfect matching in a graph depends on the parity convention. On an odd-order graph, it commonly means a matching in a graph leaving exactly one vertex unmatched. For example, a single edge of a triangle in a graph has this property.

For the even-order convention used in matching in a graph sampling, a graph with $2n$ vertices has a near-perfect matching in a graph when it has $n-1$ edges and exactly two unmatched vertices in a matching. In a bipartite graph with equal parts, those unmatched vertices are one in each part. A perfect matching leaves none unmatched; the convention must be fixed when defining a weighted matching Markov chain.