pith. sign in

arxiv: 2606.22253 · v1 · pith:SPYYLHAInew · submitted 2026-06-20 · 🧮 math.CO

On the number of perfect matchings in planar graphs

Jan Goedgebeur , Jorik Jooken , Tibo Van den Eede , Carol T. Zamfirescu This is my paper

Pith reviewed 2026-06-26 11:26 UTC · model grok-4.3

classification 🧮 math.CO
keywords planar graphsperfect matchingsconnectivityminimum numbertriangulations3-connected graphs
0
0 comments X

The pith

The smallest number of perfect matchings in 2-connected planar graphs of minimum degree 3 is constantly 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the minimum positive number of perfect matchings in planar graphs depends on connectivity. For 2-connected planar graphs with minimum degree 3, this minimum is 4 and cannot be smaller. For 3-connected planar graphs, infinite families exist with only a constant number of perfect matchings, including nearly regular graphs and triangulations. This stands in contrast to 4-connected graphs where the number grows at least linearly with size and 5-connected triangulations where it grows exponentially. Understanding these bounds clarifies how graph structure constrains the existence of perfect matchings.

Core claim

The minimum non-zero number of perfect matchings is a constant for 2-connected planar graphs of minimum degree 3, specifically 4, and this is best possible. For 3-connected planar graphs, several infinite families achieve a constant number, such as nearly 3-regular graphs and triangulations.

What carries the argument

Classification of planar graphs by levels of connectivity to determine whether the number of perfect matchings remains bounded by a constant.

If this is right

  • The bound of four is tight because explicit examples achieve exactly four perfect matchings.
  • Infinite families of 3-connected planar graphs, including triangulations, maintain only a constant number of perfect matchings.
  • The number of perfect matchings grows at least linearly once graphs are 4-connected.
  • 5-connected triangulations must contain exponentially many perfect matchings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Planarity appears necessary to keep the number of matchings constant under low connectivity, since the Zaks conjecture counterexamples are non-planar.
  • Similar constant bounds might exist for other matching-related structures such as cycle covers when connectivity is fixed.
  • Explicit constructions of 3-connected examples with exactly four matchings would tighten the connection between the 2-connected and 3-connected cases.

Load-bearing premise

Every graph under consideration must be planar and satisfy the stated connectivity and minimum-degree conditions.

What would settle it

A single 2-connected planar graph of minimum degree 3 with fewer than four perfect matchings would falsify the claim that four is the minimum.

Figures

Figures reproduced from arXiv: 2606.22253 by Carol T. Zamfirescu, Jan Goedgebeur, Jorik Jooken, Tibo Van den Eede.

Figure 1
Figure 1. Figure 1: A planar 2-connected graph with four perfect matchings, minimum degree 3, size [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: On the left-hand side, with vertices coloured red and blue, a planar bipartite 10-vertex [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A planar bipartite graph I with 18 perfect matchings. A 2-colouring is shown. Case 3. n0 = 10, c = 12 and G is a triangulation. Triangulate the graph H by adding edges between the vertices of the red partite set. This triangulation J is a planar 3-connected 10-vertex graph. All the added edges are inadmissible by Lemma 2, hence, Φ(J) = Φ(H) = 12, which solves this case for n = 10. Suppose now that n ≥ 12 a… view at source ↗
Figure 4
Figure 4. Figure 4: A planar bipartite 3-connected 20-vertex graph with 144 perfect matchings. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A planar bipartite 3-connected 22-vertex graph with 144 perfect matchings. [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A planar bipartite 3-connected n-vertex graph with n ≡4 0 and 144 perfect matchings. G4,n≡40[V (Ln−18) \ {t (1) 1 , t(2) 1 }], which is isomorphic to L ′ , only has one perfect matching, it follows that Φ(G4,n≡40) = Φ(H) 2 = 144. Suppose n ≥ 24 and n ≡4 2. Similar to the case n ≡4 0, consider Ln−20 with z (1) and z (2) as two vertices of degree 2 in Ln−20 which are at distance n−20 2 . Consider the graph c… view at source ↗
Figure 7
Figure 7. Figure 7: A planar bipartite 3-connected n-vertex graph with n ≡4 2 and 144 perfect matchings. We now prove that Φ(G4,n≡42) = 144. Let L ′′ := G4,n≡42 − H(1) − H(2). First apply Lemma 3 with H = H(1) and L = L ′′; here D = {t (1) 1 , t(1) 2 , t(1) 3 }. We denote the resulting graph by H′′. We then apply Lemma 3 with H = H(2) and L = H′′; here D = {t (2) 1 , t(2) 2 , t(2) 3 }. Since L ′′ only has one perfect matching… view at source ↗
Figure 8
Figure 8. Figure 8: On the left-hand side, a planar 20-vertex triangulation [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
read the original abstract

We investigate the minimum non-zero number of perfect matchings in planar graphs. We prove that this is a constant for 2-connected planar graphs of minimum degree 3 and 3-connected planar graphs. In the former case, the constant is 4 and this is best possible. In the 3-connected case, we give several infinite families, including nearly 3-regular graphs and triangulations with a constant number of perfect matchings. In contrast, it was known that in the 4-connected case the minimum non-zero number of perfect matchings is at least linear. For 5-connected triangulations, it follows from a result of Alahmadi, Aldred, and Thomassen that there must be exponentially many perfect matchings. The families of planar graphs we investigate here are classified by connectivity. We conclude the article with an infinite family of counterexamples to a conjecture published by Zaks; these are not planar, but very much concern connectivity constraints.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript investigates the minimum non-zero number of perfect matchings in planar graphs classified by connectivity. It claims to prove that any 2-connected planar graph of minimum degree 3 has either zero or at least four perfect matchings (with the bound tight via explicit examples), and that the corresponding minimum is a fixed constant for 3-connected planar graphs (achieved by several infinite families, including nearly 3-regular graphs and triangulations). It contrasts these with the known linear lower bound for 4-connected planar graphs and the exponential lower bound for 5-connected triangulations, and concludes with an infinite family of (non-planar) counterexamples to a conjecture of Zaks.

Significance. If the stated proofs hold, the result would sharpen understanding of how connectivity constrains the number of perfect matchings in planar graphs, providing explicit constants and families where only growth-rate results were previously known. The explicit constructions and the counterexamples to Zaks' conjecture constitute concrete, falsifiable contributions.

minor comments (2)
  1. [Abstract] Abstract: the claim that the minimum is 'a constant' for 3-connected planar graphs is stated without identifying the value of the constant or the proof technique used to establish that it is bounded.
  2. [Abstract] Abstract: no indication is given of the key lemmas, reductions, or structural arguments that establish the lower bound of 4 for the 2-connected case or the constancy for the 3-connected case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript. The recommendation of 'uncertain' appears to stem from the need to verify the proofs in detail. No specific major comments were raised in the report, so we provide no point-by-point responses below. We are prepared to address any concrete questions about the arguments or constructions if they arise in a subsequent round.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is a pure existence and lower-bound proof in graph theory. It establishes that the minimum non-zero number of perfect matchings is exactly 4 (and tight) for 2-connected planar graphs of minimum degree 3, and a fixed constant for 3-connected planar graphs, via explicit constructions and case analysis. No equations, fitted parameters, or statistical predictions appear; the constants are proven lower bounds, not outputs of any self-referential fitting or renaming step. External citations (Alahmadi et al., Zaks) are to independent prior results and do not form a self-citation chain that carries the central claim. The derivation is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated or can be extracted.

pith-pipeline@v0.9.1-grok · 5705 in / 1065 out tokens · 23285 ms · 2026-06-26T11:26:03.829016+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references

  1. [1]

    Alahmadi, R

    A. Alahmadi, R. E. L. Aldred, and C. Thomassen. Cycles in 5-connected triangulations. J. Combin. Theory Ser. B140(2020) 27–44

    2020

  2. [2]

    Brinkmann and B

    G. Brinkmann and B. D. McKay. Fast generation of planar graphs.MATCH Commun. Math. Comput. Chem.58(2007) 323–357

    2007

  3. [3]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour. Perfect matchings in planar cubic graphs.Combinatorica32 (2012) 403–424

    2012

  4. [4]

    Coolsaet, S

    K. Coolsaet, S. D’hondt, and J. Goedgebeur. House of Graphs 2.0: A database of inter- esting graphs and more.Discrete Appl. Math.325(2023) 97–107. Available at:https: //houseofgraphs.org

    2023

  5. [5]

    Edmonds, W

    J. Edmonds, W. R. Pulleyblank, and L. Lov´ asz. Brick decompositions and the matching rank of graphs.Combinatorica2(1982) 247–274. 13

    1982

  6. [6]

    Esperet, F

    L. Esperet, F. Kardoˇ s, A. D. King, D. Kr´ al’, and S. Norine. Exponentially many perfect matchings in cubic graphs.Adv. Math.227(2011) 1646–1664

    2011

  7. [7]

    S. L. Hakimi, E. F. Schmeichel, and C. Thomassen. On the number of Hamiltonian cycles in a maximal planar graph.J. Graph Theory3(1979) 365–370

    1979

  8. [8]

    X. Liu, Z. Wang, and X. Yu. Counting Hamiltonian cycles in planar triangulations.J. Combin. Theory Ser. B155(2022) 256–277

    2022

  9. [9]

    O. S. Lo and J. Qian. Hamiltonian cycles in 4-connected planar and projective planar trian- gulations with few 4-separators.SIAM J. Discrete Math.36(2022) 1496–1501

    2022

  10. [10]

    Lov´ asz

    L. Lov´ asz. On the structure of factorizable graphs.Acta Math. Hung.23(1972) 179–195

    1972

  11. [11]

    W. Mader. ¨Uber die Anzahl der 1-Faktoren in 2-fach zusammenh¨ angenden Graphen.Math. Nachr.74(1976) 217–232

    1976

  12. [12]

    Ozeki and P

    K. Ozeki and P. Vr´ ana. 2-edge-Hamiltonian-connectedness of 4-connected plane graphs.Euro- pean J. Combin.35(2014) 432–448

    2014

  13. [13]

    M. D. Plummer. Extending matchings in planar graphs IV.Discrete Math.109(1992) 207–219

    1992

  14. [14]

    Q. R. Yu and G. Liu.Graph factors and matching extensions. Springer, 2009

    2009

  15. [15]

    J. Zaks. On the 1-factors ofn-connected graphs.J. Combin. Theory Ser. B11(1971) 169–180. 14

    1971