TransWikia.com

Pairing up vertices in a graph

MathOverflow Asked on November 24, 2021

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

One 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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP