Let denote the number of perfect matchings of a graph . Goedgebeur et al. posted two questions about the perfect matchings of planar 3-connected graphs: does there exist an infinite family of matchable planar 3-connected graphs of girth 5 with a constant number of perfect matchings? Whether there exist infinitely many planar 3-connected graphs with minimum degree 5 which have a constant number of perfect matchings. We present answers to those questions. First, we construct, for every even , a simple planar 3-connected graph of order and girth five with exactly perfect matchings, where is a fixed positive integer. Second, for a simple planar 3-connected graph with a perfect matching and minimum degree at least five, we show that . This implies that, for each positive integer , only finitely many such graphs, up to isomorphism, have at most perfect matchings.

生成讲解博客的中文版本

生成AI智能校验的中文版本