Pairing up vertices in a graph

Question

Given a connected (undirected) graph with an even number of vertices, consider how many ways are there to pair up vertices so that each pair is connected by an edge. Is there a known classification of all such graphs  into those with $0$ ways, $1$ way, and more than $1$ way?
For example, a star belongs to the first category, a path to the second, and a cycle to the third (with $2$ ways).

Johan Wästlund · Answer

In general, finding the number of perfect matchings is #P-complete. But using the Edmonds "blossom" algorithm, one can decide effectively if the number is zero or not. And it's also easy using the same algorithm to figure out if the number is exactly 1 (in principle we can try removing the edges one by one and check in each case whether there is still a perfect matching). So if we just want to classify into 0, 1 or many, it's doable in polynomial time.

Answered by Johan Wästlund on November 24, 2021

Pairing up vertices in a graph

One Answer

Add your own answers!

Ask a Question