The number of perfect matchings in 3-connected planar graphs

Abstract

A graph is matchable if it admits a perfect matching. Recently, Goedgebeur et al. asked whether there exists a constant $c<12$ such that infinitely many matchable planar $3$-connected graphs, each with exactly $c$ perfect matchings. We answer this question by proving that every matchable planar $3$-connected graph on at least 40 vertices has at least 12 perfect matchings, and this lower bound is sharp.

12 pages,5 figures