Open Problem Garden

A classical theorem of Petersen [P] asserts that every cubic graph without a cut-edge has a perfect matching (nowadays this is usually derived as a corollary of Tutte's 1-factor theorem). In the 70's, Lovasz and Plummer made the above conjecture, which asserts that every such graph has exponentially many perfect matchings. Despite considerable work on the topic of perfect matchings, this conjecture remains open.

Let be an vertex cubic graph. Edmond's matching polytope theorem gives a precise description of what vectors in can be written as a convex combination of characteristic vectors of perfect matchings. Assuming this polytope is nonempty, the number of perfect matchings in is at least its dimension plus one. Using this technique, it can be shown (see [ELP] and [N]) that has matchings if it has no cut-edge, and perfect matchings if it is cyclically 4-edge-connected. Similar bounds can be achieved using Lovasz' matching lattice theorem [L]. Kral, Sereni, and Stiebitz [KSS] improved the lower bound for graphs without a cut-edge to . In fact, these authors do much more: they list all 17 of the -vertex cubic graphs which have fewer than perfect matchings. More recently, Esperet, Kardos, and Kral [EKK] proved that bridgeless cubic graphs have a superlinear number of perfect matchings.

There are two significant classes of cubic graphs for which the conjecture is known: bipartite and planar. It was proved for bipartite graphs by Voorhoeve [V], and this was later extended to general regular bipartite graphs by Schrijver [S] (see also Gurvits [G] for an interesting alternate proof). Very recently, Chudnovsky and Seymour [CS] have proved the conjecture for planar graphs.