pith. sign in

arxiv: 2605.03786 · v2 · submitted 2026-05-05 · 🧮 math.CO

A note on cycles in cyclically 4-edge-connected cubic planar graphs

On-Hei Solomon Lo This is my paper

Pith reviewed 2026-05-12 01:15 UTC · model grok-4.3

classification 🧮 math.CO
keywords cubic planar graphscyclically 4-edge-connectedcircumferencecycle lengthsline graphsThree Edge LemmaEuler's formula
0
0 comments X

The pith

If a graph H formed by deleting two adjacent vertices from a cyclically 4-edge-connected cubic planar graph has circumference at least k, then it contains a cycle whose length is between k and 3k/2.

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

The paper establishes that removing two adjacent vertices from certain cubic planar graphs produces a graph H in which a long cycle forces the existence of another cycle in a controlled length interval. The argument proceeds by applying Euler's formula together with the Three Edge Lemma to derive the bound. This yields a direct consequence for the cycle spectrum of the line graph of the original graph. The result addresses questions about the distribution of cycle lengths in planar graphs and builds on prior conjectures concerning such structures.

Core claim

Let H be obtained from a cyclically 4-edge-connected cubic planar graph Y other than K4 by deleting two adjacent vertices. If H has circumference at least k for some even integer k ≥ 4, then H contains a cycle of length between k and 3k/2. The proof combines Euler's formula and the Three Edge Lemma. As a consequence, the line graph G of Y contains a cycle of length l avoiding any prescribed vertex of G, for every l in {3} ∪ {5, …, |V(G)| − 1}.

What carries the argument

The deletion of two adjacent vertices from Y to produce H, which preserves enough structure for Euler's formula and the Three Edge Lemma to force an intermediate-length cycle when the circumference is at least k.

If this is right

  • The line graph G of Y admits a cycle of every allowed length l that misses any chosen vertex.
  • The cycle spectrum of the line graph covers all integers from 3 to |V(G)| except possibly 4.
  • The same length bound applies uniformly for every even k that is at most the circumference of H.

Where Pith is reading between the lines

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

  • The technique of vertex deletion plus Euler's formula might be adapted to study cycle lengths in graphs obtained by other small modifications of planar cubic graphs.
  • Verification on small examples such as the prism graphs or the dodecahedron could reveal whether the 3k/2 bound is sharp.
  • If the bound holds, it supplies a concrete step toward determining the full set of avoidable cycle lengths in line graphs of 4-edge-connected planar graphs.

Load-bearing premise

Y must be cyclically 4-edge-connected and cubic planar but not K4, with H formed precisely by deleting two adjacent vertices.

What would settle it

A cyclically 4-edge-connected cubic planar graph Y other than K4 such that after deleting two adjacent vertices the resulting H has circumference k yet contains no cycle whose length lies strictly between k and 3k/2.

read the original abstract

Let $H$ be obtained from a cyclically $4$-edge-connected cubic planar graph $Y$ other than $K_4$ by deleting two adjacent vertices. We provide a short proof that if $H$ has circumference at least $k$ for some even integer $k \ge 4$, then $H$ contains a cycle of length between $k$ and $3k/2$. As a consequence, we show that the line graph $G$ of $Y$ contains a cycle of length $l$ avoiding any prescribed vertex of $G$, for every $l \in \{3\} \cup \{5, \dots, |V(G)| - 1\}$. The proofs integrate Euler's formula and the Three Edge Lemma, established by Thomas and Yu, and independently by Sanders, in a novel way. This work was partially motivated by conjectures of Bondy and Malkevitch.

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 claims that if H is obtained by deleting two adjacent vertices from a cyclically 4-edge-connected cubic planar graph Y other than K4, and if the circumference of H is at least k for some even integer k ≥ 4, then H contains a cycle of length l with k ≤ l ≤ 3k/2. As a consequence, the line graph G of Y contains a cycle of length l avoiding any prescribed vertex of G, for every l in {3} ∪ {5, …, |V(G)|−1}. The proofs combine Euler's formula with the Three Edge Lemma of Thomas-Yu and Sanders.

Significance. If correct, the result supplies a concrete interval guarantee on cycle lengths in the graphs H, which immediately yields a near-complete cycle spectrum (avoiding one vertex) in the line graphs of the original cubic planar graphs. The short, self-contained argument that integrates two standard tools without introducing free parameters or ad-hoc constructions is a clear strength and directly addresses aspects of the Bondy-Malkevitch conjectures mentioned in the abstract.

minor comments (2)
  1. [Proof of Theorem 1] The precise statement of the Three Edge Lemma (including its hypotheses on the graph class) is not recalled in the manuscript; adding a one-sentence restatement before its first use would improve readability for readers who do not have the reference at hand.
  2. [Corollary 2] In the consequence for line graphs, the range begins at 3 and then jumps to 5; a brief sentence explaining why length 4 is excluded (or confirming it is impossible under the hypotheses) would clarify the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful summary of the manuscript, the positive assessment of its significance, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper delivers a short proof that if the graph H (obtained by deleting two adjacent vertices from a cyclically 4-edge-connected cubic planar graph Y ≠ K4) has circumference at least k (even k ≥ 4), then H contains a cycle of length between k and 3k/2. This is established by combining Euler's formula with the Three Edge Lemma (Thomas-Yu and Sanders, external citations with no author overlap). The consequence for line graphs of Y follows directly. No step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the derivation is self-contained against standard planar-graph tools and independent lemmas.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard Euler formula for planar graphs and the previously published Three Edge Lemma; no free parameters or new entities are introduced.

axioms (2)
  • standard math Euler's formula V - E + F = 2 for connected planar graphs
    Invoked in the short proof as described in the abstract.
  • domain assumption Three Edge Lemma (Thomas-Yu and Sanders)
    Established prior result integrated into the argument.

pith-pipeline@v0.9.0 · 5454 in / 1499 out tokens · 57950 ms · 2026-05-12T01:15:14.681409+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    J. A. Bondy. Pancyclic graphs: Recent results. In A. Hajnal, R. Rado, and V. Sós, editors, Infinite and finite sets (Colloq. Keszthely, 1973; Dedicated to P. Erdős on his 60th birthday), volume 10 ofColloq. Math. Soc. János Bolyai, pages 181–187. North-Holland, Amsterdam, 1975

    work page 1973

  2. [2]

    G. Chen, G. Fan, and X. Yu. Cycles in 4-connected planar graphs.European J. Combin., 25:763–780, 2004. 6

    work page 2004

  3. [3]

    Q. Cui, Y. Hu, and J. Wang. Long cycles in 4-connected planar graphs.Discrete Math., 309(5):1051–1059, 2009

    work page 2009

  4. [4]

    Cui and O.-H

    Q. Cui and O.-H. S. Lo. Tight gaps in the cycle spectrum of 3-connected planar graphs.SIAM J. Discrete Math., 35(3):2039–2048, 2021

    work page 2039

  5. [5]

    Fijavž, M

    G. Fijavž, M. Juvan, B. Mohar, and R. Škrekovski. Planar graphs without cycles of specific lengths.European J. Combin., 23(4):377–388, 2002

    work page 2002

  6. [6]

    S. L. Hakimi and E. F. Schmeichel. On the number of cycles of lengthkin a maximal planar graph.J. Graph Theory, 3(1):69–86, 1979

    work page 1979

  7. [7]

    O.-H. S. Lo. Find subtrees of specified weight and cycles of specified length in linear time.J. Graph Theory, 98(3):531–552, 2021

    work page 2021

  8. [8]

    O.-H. S. Lo. Cycles in 3-connected claw-free planar graphs and 4-connected planar graphs without 4-cycles.J. Graph Theory, 107(4):702–728, 2024

    work page 2024

  9. [9]

    O.-H. S. Lo and J. M. Schmidt. Cycle spectra of contraction-critically 4-connected planar graphs.Graphs Combin., 37(6):2129–2137, 2021

    work page 2021

  10. [10]

    O.-H. S. Lo and C. T. Zamfirescu. Counting cycles in planar triangulations.J. Combin. Theory Ser. B, 170:335–351, 2025

    work page 2025

  11. [11]

    Malkevitch

    J. Malkevitch. On the lengths of cycles in planar graphs. In M. Capobianco, J. Frechen, and M. Krolik, editors,Recent Trends in Graph Theory (Proc. Conf., New York 1970), volume 186 ofLecture Notes in Mathematics, page 191–195. Springer, Berlin, 1971

    work page 1970

  12. [12]

    Malkevitch

    J. Malkevitch. Cycle lengths in polytopal graphs. In Y. Alavi and D. Lick, editors,Theory and Applications of Graphs (Proc. Conf., Michigan 1976), volume 642 ofLecture Notes in Computer Science, page 364–370. Springer, Berlin, 1978

    work page 1976

  13. [13]

    Malkevitch

    J. Malkevitch. Polytopal graphs. In L. Beineke and R. Wilson, editors,Selected Topics in Graph Theory, volume 3, page 169–188. Academic Press, 1988

    work page 1988

  14. [14]

    M. D. Plummer. Problems. In A. Hajnal, R. Rado, and V. Sós, editors,Infinite and finite sets (Colloq. Keszthely, 1973; Dedicated to P. Erdős on his 60th birthday), volume 10 ofColloq. Math. Soc. János Bolyai, pages 1549–1550. North-Holland, Amsterdam, 1975

    work page 1973

  15. [15]

    D. P. Sanders. On Hamilton cycles in certain planar graphs.J. Graph Theory, 21(1):43–50, 1996

    work page 1996

  16. [16]

    Thomas and X

    R. Thomas and X. Yu. 4-connected projective-planar graphs are Hamiltonian.J. Combin. Theory Ser. B, 62:114–132, 1994

    work page 1994

  17. [17]

    Thomassen

    C. Thomassen. A theorem on paths in planar graphs.J. Graph Theory, 7(2):169–176, 1983

    work page 1983

  18. [18]

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

    work page 1956

  19. [19]

    Wang and K.-W

    W. Wang and K.-W. Lih. Choosability and edge choosability of planar graphs without 5-cycles. Appl. Math. Lett., 15(5):561–565, 2002

    work page 2002

  20. [20]

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

    work page 1931