= 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>.
Back to article page
