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).



Pairing up vertices in a graph
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.


