Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: June 30th, 2008
Solved by: L. Esperet, F. Kardoš, A. D. King, D. Král', S. Norine. Exponentially many perfect matchings in cubic graphs. Advances in Mathematics, to appear, 2011. DOI: 10.1016/j.aim.2011.03.015
Conjecture   There exists a fixed constant $ c $ so that every $ n $-vertex cubic graph without a cut-edge has at least $ e^{cn} $ perfect matchings.

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 $ G = (V,E) $ be an $ n $ vertex cubic graph. Edmond's matching polytope theorem gives a precise description of what vectors in $ {\mathbb R}^{E} $ can be written as a convex combination of characteristic vectors of perfect matchings. Assuming this polytope is nonempty, the number of perfect matchings in $ G $ is at least its dimension plus one. Using this technique, it can be shown (see [ELP] and [N]) that $ G $ has $ \ge n/4 + 2 $ matchings if it has no cut-edge, and $ \ge n/2 + 1 $ 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 $ n/2 $. In fact, these authors do much more: they list all 17 of the $ n $-vertex cubic graphs which have fewer than $ n/2 + 2 $ 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.


[CS] M. Chudnovsky and P. Seymour. Perfect matchings in planar cubic graphs.

[EKK] L. Esperet, F. Kardos, D. Kral'. A superlinear bound on the number of perfect matchings in cubic bridgeless graphs.

[KSS] D. Kral, J.-S. Sereni, and M. Stiebitz, A new lower bound on the number of perfect matchings in cubic graphs.

[P] J. Petersen, Die Theorie der regularen graphs. Acta Math., 15(1):193–220, 1891.

[ELP] J. Edmonds, L. Lovasz, and W. R. Pulleyblank. Brick decompositions and the matching rank of graphs. Combinatorica, 2(3):247–274, 1982.

[G] L. Gurvits. Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 417–426, New York, 2006. ACM.

[L] L. Lovasz. Matching structure and the matching lattice. J. Combin. Theory Ser. B, 43(2):187–222, 1987.

[N] D. Naddef. Rank of maximum matchings in a graph. Math. Programming, 22(1):52–70, 1982.

[S] A. Schrijver. Counting 1-factors in regular bipartite graphs. J. Combin. Theory Ser. B, 72(1):122–135, 1998.

[V] M. Voorhoeve. A lower bound for the permanents of certain (0, 1)-matrices. Nederl. Akad. Wetensch. Indag. Math., 41(1):83–86, 1979.

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options