For bipartite graphs, there’s Hall’s theorem: https://en.wikipedia.org/wiki/Hall's_marriage_theorem For general graphs, there isn’t a simple condition, but there is a polynomial-time algorithm: namely Edmond’s “Paths, Trees, and Flowers” algorithm. In fact this is often quoted as one of the first papers that talks abstractly about the class P of problems solvable in polynomial time. - Cris

On Dec 20, 2020, at 1:00 PM, Dan Asimov <asimov@msri.org> wrote:

For a finite graph G (assume G is connected and without loops or multiple edges), a "perfect matching" is a set of disjoint edges all of whose endpoints form the vertex set V(G) of G.

(Fun exercise: For each of the five Platonic solids, the graph of its edges has a perfect matching.)

Obviously, a *necessary* condition for G to have a perfect matching is that |V(G)| be *even*.

Question: --------- Is a simple sufficient condition for G to have a perfect matching known?

(A vertex v contained in only one edge e of G would force e to be in any perfect matching, and this leads to easy counterexamples, like the Y-shaped graph on 4 vertices.

(So let's also assume there are no vertices contained in only one edge.)

—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fmailman.xmission.com%2fc...