{"id":"e60cbf6c-81e1-456f-b508-276512c798f1","arxiv_id":"2507.18090","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In 5-connected planar triangulations, the maximum number of 5-cycles is 9n-50, and for k≥6 the maximum number of k-cycles is Θ(n^{⌊k/3⌋}).","lead":"This paper proves that every 5-connected planar triangulation on n vertices has at most 9n-50 cycles of length 5, and that cycles of length k≥6 are at most O(n^{⌊k/3⌋}); both bounds are tight. It resolves a question about how much stronger connectivity suppresses cycle counts in planar graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The induction rests on an undescribed computer search for n≤20; an error in that table would invalidate Theorem 1, so the base cases should be independently verified.","rationale":"The central claim of the paper is an exact extremal theorem, and the proof is an induction whose base is supplied entirely by computer search. Since the search is not described and the code is not pinned, the theorem is not currently checkable from the text alone; this matches the reader's weakest-assumption identification. I agree with the conditional verdict: the analytic parts are broadly plausible, in particular the correction of the 3/2 typo restores the 6n−12 non-separating count used throughout, and the k-cycle proof in Section 4 checks out for all three residue classes with the same counting scheme, but the base-case values remain the single most consequential unresolved item. An independent enumeration would settle the question.","tokens_in":17580,"tokens_out":36518,"duration_ms":383750,"concrete_test":"Run an independent enumeration of all 5-connected planar triangulations on 12≤n≤20, for example by generating all plane triangulations with plantri, filtering for 5-connectivity, and computing the maximum number of 5-cycles and of separating 5-cycles with a separate script. Compare every row of Table 1, and verify that a 20-vertex graph of the claimed extremal type D1 attains exactly 130 5-cycles and that no other 20-vertex graph exceeds it. Also re-run the authors' GitHub program and diff its output against this independent enumeration; if all values match, the computational premise is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is the computer-generated base case for n≤20 (footnote 1). Theorem 1 is proved by induction from Table 1, and the inductive reductions in Case 1 and Case 2 explicitly reuse the table whenever the reduced graph G′ has n′≤19, so a single erroneous entry in N5(C5,n) or in the separating-cycle column can propagate to every n≥21. The paper gives no description of the search algorithm, no version or hash of the code, and no independent confirmation of the listed maxima. This is the least secure point of the argument: the analytic lemmas (Observation 1, Lemma 4, and the structure analysis in Cases 1 and 2) are coherent, but they cannot repair a wrong base. A separate arithmetic typo appears in the non-separating 5-cycle count, where (2n−4)·(3/2) is written equal to 6n−12; the intended factor is evidently 3, and this does not affect the main concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17767,"tokens_out":27716,"duration_ms":279666,"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":[{"comment":"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.","section":"Section 3, Table 1 and footnote 1"},{"comment":"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.","section":"Section 3, proof of Theorem 1 (non-separating 5-cycle count)"}],"minor_comments":[{"comment":"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.","section":"Section 3, Case 1"},{"comment":"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.","section":"Section 4, Theorem 3"},{"comment":"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.","section":"Section 2, Lemma 6"},{"comment":"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.","section":"Section 1, Figure 1"},{"comment":"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).","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the computer-generated base table: if the authors supply a reproducible and independently verifiable description of the search, the paper should be acceptable for a combinatorics journal. The structural proofs are coherent, and no circularity or fitted parameters are apparent. The GitHub link should be archived (e.g., on a permanent repository) before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuinely new result. Prior to it, even the order of N5(C5,n) was open. The paper determines it exactly for n≥20 (9n−50, tight, unique extremal graphs D1/D2) and shows N5(Ck,n)=Θ(n^{floor(k/3)}) for k≥6, contrasting with the Θ(n^{floor(k/2)}) behavior for 4-connected triangulations. Theorem 3 is a real strengthening of the Győri et al. C4-free bound to graphs with at most two common neighbors, and the proof is self-contained given Lemma 5.\n\nThe structure of the proof of Theorem 1 is coherent: the reduction in Case 1 and the contraction argument in Case 2 are the right tools, and the counting checks out once the typo in the non-separating 5-cycle count is corrected. The paper writes (2n−4)·(3/2)=6n−12; the intended factor is 3, and the claimed value is correct with that factor. Minor.\n\nThe soft spots are real but not fatal. The base cases for n≤20 come from a computer search that is not described in the paper. Footnote 1 gives a GitHub link but no algorithm description, no code version, and no hash. The induction in Theorem 1 reuses Table 1 whenever the reduced graph has n′≤19, so a single wrong entry would propagate to every n≥21. That makes the table load-bearing. It deserves independent verification before publication. The rest of the case analysis is long, but I did not find a gap; the most delicate part is the uniqueness of the extremal graphs, and that argument is supported by the structural claims in the final paragraph of Case 2.\n\nThe paper is honest with its references: Lemma 5 is credited to Barnette and Borodin, and the proof of Theorem 3 explicitly says it follows the lines of Theorem 10 in [13]. No fitted parameters, no circularity. This is a serious paper.\n\nWho is it for? Extremal and structural graph theorists. A referee should check the base-case search, verify Table 1 for n≤20, and read the Case 2 minimality argument carefully. I would send it to review. Conditional acceptance with a request for code details and independent verification would be appropriate.","headline":"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.","tokens_in":18346,"tokens_out":1741,"would_cite":true,"duration_ms":18494,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C35","05C38","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["5-connected planar triangulations","cycle enumeration","pentagon counts","extremal graph theory","planar Turán numbers","degree-sum lemma","common neighbours","separating cycles"],"falsifier":"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.","tokens_in":2053,"feed_emoji":"🔺","tokens_out":2250,"duration_ms":98995,"temperature":0.7,"pith_summary":"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.","feed_headline":"5-connectivity cuts planar k-cycle exponent to ⌊k/3⌋","feed_subtitle":"The 5-cycle maximum is exactly 9n−50 for n≥20, with unique extremal graphs, and longer cycles are bounded by C(k)n^{⌊k/3⌋}.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Establishes the general planar maxima $\\Theta(n^{\\lfloor k/2 \\rfloor})$ and the exact triangle and 4-cycle counts that frame the connectivity contrast.","marker":"[15]"},{"why":"Gives the extremal number of pentagons in planar graphs and the double-wheel extremal example that Theorem 1 refines under 5-connectivity.","marker":"[14]"},{"why":"Provides the $C_4$-free planar upper bound $O(n^{\\lfloor k/3 \\rfloor})$ whose proof template Theorem 3 follows and strengthens.","marker":"[13]"},{"why":"Supplies the planar degree-sum fact (an edge with degree sum at most 13) that Lemma 6 uses after suppressing degree-2 vertices.","marker":"[12]"},{"why":"Independent source of the same degree-sum fact, also cited for Lemma 5.","marker":"[7]"}],"fun_headline_variants":["5-connected planar graphs cap k-cycles at floor(k/3)","Exact pentagon count: 9n−50 for n≥20","Tight bound on k-cycles in 5-connected planar graphs","Planar triangulations: max pentagons is 9n−50","k-cycle exponent drops to floor(k/3) in 5-connected planar graphs"],"cache_read_input_tokens":20480,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["5-connected planar graphs cap k-cycles at floor(k/3)","Exact pentagon count: 9n−50 for n≥20","Tight bound on k-cycles in 5-connected planar graphs","Planar triangulations: max pentagons is 9n−50","k-cycle exponent drops to floor(k/3) in 5-connected planar graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1346,"prompt_tokens":942,"completion_tokens":404,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":306}},"tokens_in":558,"tokens_out":404,"duration_ms":4571,"temperature":1.0,"reasoning_tokens":306,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:41:49.761594+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Hakimi and E","cited_arxiv_id":null,"evidence_quote":"Establishes the general planar maxima $\\Theta(n^{\\lfloor k/2 \\rfloor})$ and the exact triangle and 4-cycle counts that frame the connectivity contrast."},{"cited_title":"Gy˝ ori, A","cited_arxiv_id":null,"evidence_quote":"Gives the extremal number of pentagons in planar graphs and the double-wheel extremal example that Theorem 1 refines under 5-connectivity."},{"cited_title":"Gy˝ ori, A","cited_arxiv_id":null,"evidence_quote":"Provides the $C_4$-free planar upper bound $O(n^{\\lfloor k/3 \\rfloor})$ whose proof template Theorem 3 follows and strengthens."},{"cited_title":"Gr¨ unbaum, New views on some old questions of combinatorial geometry, Int","cited_arxiv_id":null,"evidence_quote":"Supplies the planar degree-sum fact (an edge with degree sum at most 13) that Lemma 6 uses after suppressing degree-2 vertices."},{"cited_title":"Borodin, On the total coloring of planar graphs, J","cited_arxiv_id":null,"evidence_quote":"Independent source of the same degree-sum fact, also cited for Lemma 5."}],"review_version":1}