20 Dec
2020
20 Dec
'20
1 p.m.
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