Pith. sign in

REVIEW 2 major objections 5 minor 31 references

Counting $k$-cycles in $5$-connected planar triangulations

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every n-vertex 5-connected planar triangulation has at most 9n−50 five-cycles, and 5-connected planar graphs have at most C(k)n^{⌊k/3⌋} cycles of length k.

desk verdict New exact extremal count for 5-cycles in 5-connected planar triangulations, with a clean generalization for longer cycles, but the proof leans on an unverified computer search for n≤20. read the letter →

arxiv 2507.18090 v2 pith:34TVQFRR submitted 2025-07-24 math.CO

Gyaneshwar Agrahari , Xiaonan Liu , Zhiyu Wang This is my paper · ORCID
classification math.CO MSC 05C1005C3505C3805C40
keywords 5-connectedplanartriangulationscycleenumerationpentagoncountsextremalgraphtheoryTuránnumbersdegree-sumlemmacommonneighboursseparatingcycles
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines exactly how many 5-cycles a 5-connected planar triangulation can contain and gives the order of growth for cycles of every fixed length at least 6. For $n \ge 20$, every such triangulation on $n$ vertices has at most $9n-50$ cycles of length 5, and the bound is tight, with the graphs $D_1$ (even $n$) and $D_2$ (odd $n$) as the unique extremal examples. For every $k \ge 6$, any $n$-vertex 5-connected planar graph has at most $C(k)n^{\lfloor k/3 \rfloor}$ cycles of length $k$, and this exponent is asymptotically tight. The contrast with ordinary planar graphs, where the maximum is $\Theta(n^{\lfloor k/2 \rfloor})$, is the main point: 5-connectivity lowers the exponent from $\lfloor k/2 \rfloor$ to $\lfloor k/3 \rfloor$. The engine is a stronger counting theorem for $m$-edge planar graphs whose vertex pairs share at most two common neighbours.

What carries the argument

For the 5-cycle theorem, the load-bearing object is the closed interior $H := \overline{C}$ of a vertex-minimal non-trivial separating 5-cycle $C$. Lemma 4 says such an interior has at least 11 vertices and is exactly the fixed 11-vertex near triangulation $G_{11}$ when it has 11 vertices; this lets the proof replace larger interiors by $G_{11}$ while preserving 5-connectivity, because any crossing 4-cycle would force a forbidden length-two path between non-adjacent boundary vertices. For the $k \ge 6$ theorem, the machinery is a degree-sum lemma: a planar graph with minimum degree at least 2 and at most two common neighbours per vertex pair contains an edge with degree sum at most 39, obtained by suppressing degree-2 vertices and applying a standard planar degree-sum bound. The counting then enumerates $k$-cycles by selecting every third edge and using the bounded common-neighbour condition to limit the remaining vertex choices.

What would settle it

Independently enumerate all 5-connected planar triangulations on 12 through 20 vertices and compare the maximum number of 5-cycles and of separating 5-cycles with the values in Table 1 (72, 84, 90, 98, 103, 112, 122, 130); any discrepancy would refute the induction base for Theorem 1. For Theorem 2, an explicit 5-connected planar triangulation with more than $C(k)n^{\lfloor k/3 \rfloor}$ $k$-cycles for some fixed $k$ would refute the bound.

Watch

Extended reading notes

Core claim

The paper's central discovery is an exact extremal theorem for pentagons and an asymptotic theorem for longer cycles in 5-connected planar graphs. Theorem 1 states that for $n \ge 20$, every $n$-vertex 5-connected planar triangulation has at most $9n-50$ 5-cycles, that this upper bound is attained, and that the extremal graphs are $D_1$ for even $n$ and $D_2$ for odd $n$; exact values for $n \le 19$ are listed from a computer search that also supplies the induction base. Theorem 2 states that for every fixed $k \ge 6$, every sufficiently large $n$-vertex 5-connected planar graph contains at most $C(k)n^{\lfloor k/3 \rfloor}$ cycles of length $k$. The paper proves the stronger Theorem 3: any $m$-edge planar graph in which every two vertices have at most two common neighbours has at most $(342 \cdot 4^{\lfloor k/3 \rfloor}/\lfloor k/3 \rfloor!)\, m^{\lfloor k/3 \rfloor}$ cycles of length $k$. Since 5-connected planar graphs satisfy the common-neighbour condition and have at most $3n-6$ edges, Theorem 2 follows directly.

Load-bearing premise

The induction for Theorem 1 starts from a finite set of extremal values for $n \le 20$ produced by a computer search; if that search is wrong, the claimed bound for all larger $n$ has no basis in the proof as written.

Editorial extensions

If this is right

  • For every $n \ge 20$, the maximum number of 5-cycles in an $n$-vertex 5-connected planar triangulation is exactly $9n-50$, with $D_1$ and $D_2$ the unique extremal graphs.
  • For each fixed $k \ge 6$, any 5-connected planar graph on $n$ vertices has at most $C(k)n^{\lfloor k/3 \rfloor}$ cycles of length $k$, so 5-connectivity lowers the exponent from the general planar $\Theta(n^{\lfloor k/2 \rfloor})$ bound.
  • Both bounds are asymptotically tight: width-$w$ inflated blow-ups of $C_{\lfloor k/3 \rfloor}$ give $\Omega(n^{\lfloor k/3 \rfloor})$ $k$-cycles for $k \ge 9$, and $D_1$ or $D_2$ give $\Omega(n^2)$ cycles of lengths 6, 7, and 8.
  • Theorem 3 strengthens the known $O(n^{\lfloor k/3 \rfloor})$ bound for $C_4$-free planar graphs to all planar graphs whose vertex pairs have at most two common neighbours, a class that includes every 5-connected planar graph.
  • Adapting the degree-sum lemma gives the same $O(n^{\lfloor k/3 \rfloor})$ order for $k$-cycles in $K_{2,t}$-free planar graphs for every fixed $t \ge 2$ and $k \ge 5$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A stability version of Theorem 1 is plausible: the equality analysis in the $n' = 12$ case suggests that graphs with close to $9n$ 5-cycles must resemble $D_1$ or $D_2$, but the paper does not state such a result.
  • The constant 342 in Theorem 3 comes from rounding $39^2/4 - 39 + 1 = 342.25$ down, so sharpening the degree-sum threshold in Lemma 6 would improve the constant; the paper leaves the optimal $C(k)$ open.
  • The same common-neighbour counting scheme should apply to graph classes with bounded genus or bounded treewidth whenever a suitable degree-sum lemma exists; the paper only claims the planar setting.
  • Making the computer base case reproducible by specifying the search algorithm would turn Theorem 1 into a fully checkable statement, and an independent implementation would settle whether the listed extremal values for $n \le 20$ are correct.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper determines the maximum number of 5-cycles in an n-vertex 5-connected planar triangulation: Theorem 1 states that for n >= 20 this number is at most 9n - 50, that the bound is tight, and that the extremal graphs are uniquely the two graphs D1 (n even) and D2 (n odd) shown in Figure 1. The proof is a structural induction that reduces a putative extremal graph to a smaller 5-connected triangulation, with base values for n <= 20 taken from a computer search summarized in Table 1 and linked in footnote 1. The paper also proves Theorem 2, asserting that for every k >= 6 every n-vertex 5-connected planar graph has at most C(k) n^{floor(k/3)} cycles of length k, and Theorem 3, a more general bound of the same order for m-edge planar graphs in which every pair of vertices has at most two common neighbors. Construction of inflated blow-ups of cycles is used to show that the order n^{floor(k/3)} is asymptotically tight.

Significance. If the computer-assisted base cases are accepted, the paper gives the first exact extremal result for 5-cycles under 5-connectivity, with a uniqueness characterization, and it establishes a dramatic gap between 4-connected and 5-connected planar triangulations: the exponent drops from floor(k/2) to floor(k/3) for all k >= 6. Theorem 3 is a genuine strengthening of the known C4-free planar bound of Győri, Paulos, Salia, Tompkins, and Zamora, replacing the common-neighbor bound 1 by 2, with an explicit constant; the proof is largely self-contained and rests on the published Barnette-Borodin light-edge lemma. The structural lemmas (Observation 1, Lemma 4, Observation 2, Lemma 6) are coherent, the induction arithmetic is consistent once the typo in the non-separating count is corrected, and the paper explicitly identifies the main computational premise, which is the right place to anchor scrutiny.

major comments (2)
  1. [Section 3, Table 1 and footnote 1] The proof of Theorem 1 is an induction that explicitly reuses Table 1 whenever a reduced graph G' has n' <= 19, in both Case 1 and Case 2. The table is asserted to be determined by computer search (footnote 1), but the manuscript does not describe the search algorithm, does not state how the values of N5(C5, n) and the maximum number of separating 5-cycles were verified, and does not pin a version of the linked code. Since a single erroneous entry in either column of Table 1 would propagate to every n >= 21, this is a load-bearing premise. Please provide a full description of the enumeration and counting procedure (e.g., generating all 5-connected planar triangulations on 12 to 20 vertices with plantri or an equivalent exact method, checking 5-connectivity, and computing both the total number of 5-cycles and the number of separating 5-cycles), an independent verification method or certificates for the listed maxima, and a commit hash or permanent archive of the code.
  2. [Section 3, proof of Theorem 1 (non-separating 5-cycle count)] The line asserting that the number of non-separating 5-cycles is exactly (2n - 4) * (3/2) = 6n - 12 is arithmetically inconsistent, since (2n - 4) * (3/2) = 3n - 6. The subsequent reduction to bounding the number of separating 5-cycles by 3n - 38 depends on the value 6n - 12, so the intended factor is evidently 3, giving (2n - 4) * 3 = 6n - 12. Please correct this typo and add a short derivation of the count 6n - 12; as written, the claim that each of the 2n - 4 facial triangles contributes exactly three non-separating 5-cycles is not self-evident and is load-bearing for the proof.
minor comments (5)
  1. [Section 3, Case 1] The inequality '|V(D1)| < |V(C)|' is false if V(D1) and V(C) denote the vertex sets of the two 5-cycles, since both have five vertices; it should refer to the numbers of vertices in the closed interiors of D1 and C, which is the vertex-minimality criterion used to choose C.
  2. [Section 4, Theorem 3] The case k ≡ 1 (mod 3) is dismissed as 'near identical' to the case k ≡ 2 (mod 3); please spell out the counting for k = 3p + 1 explicitly, or at least state the exact analogue of the edge-selection step, so that the constant C(k) is seen to work for this case as well.
  3. [Section 2, Lemma 6] The statement that 'every two vertices in G have at most two paths between them with all the internal vertices being degree two' is used to justify the factor 3 in d_G(x) <= 3 d_{G'}(x), but it is not proved; a one-sentence justification (such paths must have length two because no two degree-2 vertices are adjacent, hence they correspond to common neighbors) would remove a gap in the exposition.
  4. [Section 1, Figure 1] The extremal graphs D1 and D2 are defined only pictorially; a formal definition (for instance, as double wheels of the appropriate parity with one additional edge) would make the uniqueness statement in Theorem 1 and the claim that D1 and D2 contain Ω(n^2) cycles of lengths 6, 7, and 8 easier to check.
  5. [References] The citation 'proved (but never published) by Barnette [12]' points to [12], which is a paper by Grünbaum; please clarify that [12] is the published source reporting Barnette's proof, and check the formatting of reference [7] ('J. Reine Angew. Math. 394)' contains a stray parenthesis).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from external results and independent computer-generated base cases.

full rationale

The paper's central claim (Theorem 1) is proved by induction whose base values for n≤20 are obtained from an external computer search (footnote 1, with code link), not from the target bound; the induction step bounds separating 5-cycles using structural lemmas (Observation 1, Lemma 4, Observation 2) that are proved in the paper from planarity and 5-connectivity. The non-separating 5-cycle count is a direct combinatorial count, and the separating-cycle reductions do not reintroduce the bound being proved except through the induction hypothesis. Theorem 3 is proved from Lemma 5 (Barnette/Borodin, published external results) and Lemma 6, which is derived in the paper; the authors explicitly note that their proof follows the lines of the external result [13] but adds a new lemma, so no result is imported from self-citation as a forced premise. The few self-citations ([22], [23]) appear only as context on Hamiltonian cycles and are not load-bearing for the k-cycle theorems. The reliance on an undocumented computer search for n≤20 is a reproducibility concern, not a circularity: an erroneous table entry would falsify the induction base, but the table is not logically defined in terms of the theorem's conclusion.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claims rest on the standard degree-sum lemma of Barnette-Borodin and on a computer-verified base case table. No free parameters or new entities are introduced.

assumptions (2)
  • domain assumption The computer search correctly computes N5(C5,n) for all n≤20 and the maximum separating 5-cycle counts in Table 1.
    Used as base cases for the induction in Theorem 1; the paper provides only a GitHub link, no algorithm description or output data, so correctness is assumed.
  • standard math Lemma 5 (Barnette-Borodin): every planar graph with minimum degree at least 3 has two adjacent vertices with degree sum at most 13.
    Cited from [12,7] and used to prove Lemma 6, which drives Theorem 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counting $k$-cycles in $5$-connected planar triangulations." pith.science (2026). https://pith.science/paper/34TVQFRR

@misc{pith2026250718090,
  author       = {Pith},
  title        = {Pith review of: Counting $k$-cycles in $5$-connected planar triangulations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/34TVQFRR}},
  note         = {Machine review of arXiv:2507.18090}
}
abstract

We show that every $n$-vertex $5$-connected planar triangulation has at most $9n-50$ many cycles of length $5$ for all $n\ge 20$ and this upper bound is tight. We also show that for every $k\geq 6$, there exists some constant $C(k)$ such that for sufficiently large $n$, every $n$-vertex $5$-connected planar graph has at most $C(k) \cdot n^{\lfloor{k/3}\rfloor}$ many cycles of length $k$. This upper bound is asymptotically tight for all $k\geq 6$.

Figures

Figures reproduced from arXiv: 2507.18090 by the authors.

Figure 1
Figure 1. Extremal graphs D1 and D2 of Theorem 1 when n is even and odd respectively. The vertices v and v ′ are adjacent, as indicated by the two half lines. For n ≤ 19, the values of N5(C5, n) are listed in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Diamond graph on 18 vertices (left); a width-5 inflated blow-up of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The graph G11. (i) C is a cycle with no chord, i.e., G[V (C)] = C, and every vertex in C has degree at least three and every vertex in G − C has degree at least five in G; (ii) and if C is the unique special 5-cycle in G, every vertex in C has degree at least four in G. Proof. Suppose G is an n-vertex near triangulation with no separating triangle or 4-cycle such that its outer cycle C = v1v2v3v4v5v1 and n ≥ 6. It f… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Hi with outer cycle Ci = uiai−1bi−1ci−1di−1ui for i ∈ [t] Recall that Ci = uiai−1bi−1ci−1di−1ui for each i ∈ [t]. We first show that for each i ∈ [t], every special 5-cycle D in Hi such that D contains the vertex ui must use the edges uiai−1, uidi−1. Suppose not and th…
Figure 5
Figure 5. Figure 5: Case x1 = a0 (left) and Case x1 = b0 (right) Let D be a special 5-cycle containing u2 in H2 such that D ̸= C2 (if D exists). Note that C2 = u2a1b1c1d1u2 is the outer cycle of H2, NH2 (u2) = {x1, a1, d1} and D should use the edges u2a1, u2d1. Recall that C1 = u1a0b0c0d0…
Figure 6
Figure 6. Figure 6: Case up = ap (left) and Case up = bp (right) Suppose ℓi ≥ 3 for some i ∈ [2, t]. Let p be the minimum integer such that ℓp+1 ≥ 3. Since ℓ0 = 1, ℓ1 = 1 and ℓ2 ≤ 2, we know that p ≥ 2. Note that up ∈ V (Cp) = {xp, ap, bp, cp, dp} and up ̸= xp by the process. Suppose up =…
Figure 7
Figure 7. Figure 7: Graphs H2 (left), H3 (middle), H4 (right). Borodin [7] (see [18] for more history). Lemma 5. [12, 7] Let G be a planar graph with minimum degree at least 3. Then G contains two adjacent vertices u and v such that d(u) + d(v) ≤ 13. Based on Lemma 5, we show the followin…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [13]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora, Generalized Planar Tur´ an Num- bers, Electron. J. Comb. , 28(4) (2021), P4.32

    work page 2021

  2. [1]

    Alahmadi, R.E.L

    A. Alahmadi, R.E.L. Aldred, R. dela Cruz, P. Sol´ e, C. Thomassen, The maximum number of minimal codewords in long codes, Discrete Appl. Math. 161 (2013) 424–429

    work page 2013

  3. [2]

    Alahmadi, R.E.L

    A. Alahmadi, R.E.L. Aldred, R. dela Cruz, P. Sol´ e, C. Thomassen, The maximum number of minimal codewords in an [ n, k]-code, Discrete Math. 313 (2013) 1569–1574

    work page 2013

  4. [3]

    Alahmadi, R.E.L

    A. Alahmadi, R.E.L. Aldred, R. dela Cruz, S. Ok, P. Sol´ e, C. Thomassen, The minimum number of minimal codewords in an [ n, k]-code and in graphic codes, Discrete Appl. Math. 184 (2015) 32–39

    work page 2015

  5. [4]

    Alahmadi, R

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

    work page 2020

  6. [5]

    Alon and Y.Caro, On the Number of Subgraphs of Prescribed Types of Planar Graphs with a Given Number of Vertices, Ann

    N. Alon and Y.Caro, On the Number of Subgraphs of Prescribed Types of Planar Graphs with a Given Number of Vertices, Ann. Discrete Math , 20 (1984),25-36

    work page 1984

  7. [6]

    B¨ ohme, J

    T. B¨ ohme, J. Harant, and M. Tk´ aˇ c, On certain Hamiltonian cycles in planar graphs,J. Graph Theory 32 (1999) 81–96

    work page 1999

  8. [7]

    Borodin, On the total coloring of planar graphs, J

    O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394) (1989) 180–185

    work page 1989

Show all 31 references
  1. [8]

    Brinkmann, J

    G. Brinkmann, J. Souffriau, and N. Van Cleemput, On the number of Hamiltonian cycles in triangulations with few separating triangles, J. Graph theory 87 (2018) 164–175

    2018

  2. [9]

    Cox and R.R

    C. Cox and R.R. Martin, Counting paths, cycles and blow-ups in planar graphs, J. Graph Theory, 101(3) (2022), 521–558. 15

    2022

  3. [10]

    Cox and R.R

    C. Cox and R.R. Martin, The maximum number of 10- and 12-cycles in a planar graph, Discrete Math., 346(2) (2023), 113245

    2023

  4. [11]

    Eppstein, Connectivity, graph minors, and subgraph multiplicity, J

    D. Eppstein, Connectivity, graph minors, and subgraph multiplicity, J. Graph Theory 17(3) (1993), 409–416

    1993

  5. [12]

    Gr¨ unbaum, New views on some old questions of combinatorial geometry, Int

    B. Gr¨ unbaum, New views on some old questions of combinatorial geometry, Int. Teorie Com- binatorie, Rome, 1973(1) (1976) 451—468

    1976

  6. [14]

    Gy˝ ori, A

    E. Gy˝ ori, A. Paulos, N. Salia, C. Tompkins, and O. Zamora, The Maximum number of Pen- tagons in a Planar Graph, J. Graph Theory , 108(2) (2025), 229-256

    2025

  7. [15]

    Hakimi and E

    S. Hakimi and E. Schmeichel, On the Number of Cycles of length k in a Maximal Planar Graph, J. Graph Theory , 3 (1979), 69–86

    1979

  8. [16]

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

    1979

  9. [17]

    Heath, R.R

    E. Heath, R.R. Martin and C. Wells, The maximum number of odd cycles in a planar graph, J. Graph Theory , 108(4) (2025), 745–780

    2025

  10. [18]

    Jendrol’ and H.-J

    S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane–A survey,Discrete Math. 313(4) (2023) 406–421

    2023

  11. [19]

    Huynh, G

    T. Huynh, G. Joret, D. Wood, Subgraph densities in a surface, Comb. Probab. Comput. 31(5) (2022), 812-839

    2022

  12. [20]

    Huynh, D

    T. Huynh, D. Wood, Tree densities in sparse graph classes, Can. J. Math. 74(5) (2022), 1385–1404

    2022

  13. [21]

    Liu, Homomorphism counts in robustly sparse graphs, arXiv:2107.00874

    C. Liu, Homomorphism counts in robustly sparse graphs, arXiv:2107.00874

    arXiv

  14. [22]

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

    2022

  15. [23]

    Liu and X

    X. Liu and X. Yu, Number of Hamiltonian cycles in planar triangulations, SIAM J. Discrete Math., 35(2) (2021), 10.1137/20M1366551

    2021 doi

  16. [24]

    O. S. Lo, Hamiltonian cycles in 4-connected plane triangulations with few 4-separators, Dis- crete Math. 343 (2020) 112126

    2020

  17. [25]

    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(2) (2022) 10.1137/21M1419556

    2022 doi

  18. [26]

    O. S. Lo and C. Zamfirescu, Counting cycles in planar triangulations, J. Combin. Theory Ser. B, 170 (2025), 335–351

    2025

  19. [27]

    Z. Lv, E. Gy˝ ori, Z. He, N. Salia, C. Tompkins, and X. Zhu, The Maximum Number of Copies of an Even Cycle in a Planar Graph, J. Comb. Theory Ser. B , 167 (2024), 15-22

    2024

  20. [28]

    J. W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. (1963), 629–631. 16

    1963

  21. [29]

    W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116

    1956

  22. [30]

    Whitney, A theorem on graphs, Ann

    H. Whitney, A theorem on graphs, Ann. Math. 32(2) (1931) 378–390

    1931

  23. [31]

    Wormald, On the frequency of 3-connected subgraphs of planar graphs, Bull

    N. Wormald, On the frequency of 3-connected subgraphs of planar graphs, Bull. Aust. Math. Soc. 34(2) (1986), 309–317. 17

    1986

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.