pith. sign in

arxiv: 2605.21165 · v1 · pith:AZ4TTUI7new · submitted 2026-05-20 · 🧮 math.CO

On k-connected vertex-pancyclic graphs without pancyclic edges

Leyou Xu , Bo Zhou This is my paper

Pith reviewed 2026-05-21 03:23 UTC · model grok-4.3

classification 🧮 math.CO
keywords k-connected graphsvertex-pancyclic graphspancyclic edgescycle lengthsgraph constructionscounterexamples
0
0 comments X

The pith

For every k there exists a k-connected vertex-pancyclic graph with no pancyclic edge.

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

The paper shows that connectivity alone does not force the existence of pancyclic edges even in vertex-pancyclic graphs. An edge is pancyclic if it belongs to a cycle of every length from 3 up to the total number of vertices; a graph is vertex-pancyclic if every vertex lies in such a full range of cycles. The authors give explicit constructions that remain k-connected and vertex-pancyclic for any chosen k yet contain no edge that spans all cycle lengths. This directly negates the possibility that some sufficiently large k would guarantee a pancyclic edge in every vertex-pancyclic graph, resolving a question left open by Zhan.

Core claim

For every positive integer k there exists a k-connected vertex-pancyclic graph on n vertices that contains no pancyclic edge. The proof proceeds by constructing suitable families of graphs and verifying that they satisfy the three required properties simultaneously: k-connectivity, the vertex-pancyclic condition, and the absence of any edge that lies in cycles of every length between 3 and n.

What carries the argument

Explicit constructions of families of graphs that are simultaneously k-connected and vertex-pancyclic while ensuring no edge participates in cycles of all lengths from 3 to n.

If this is right

  • The existence of a pancyclic edge is independent of the connectivity parameter k inside the class of vertex-pancyclic graphs.
  • Zhan's question receives a negative answer for every positive integer k.
  • Any conjecture claiming that sufficiently high connectivity forces pancyclic edges in vertex-pancyclic graphs is false.

Where Pith is reading between the lines

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

  • The same construction technique may separate connectivity from other cycle properties such as edge-pancyclicity.
  • It would be natural to ask for the minimum number of pancyclic edges that must appear in any k-connected vertex-pancyclic graph.
  • Analogous counterexamples could be sought in directed graphs or in hypergraphs with suitable pancyclicity notions.

Load-bearing premise

The specific graph families built for each k are both k-connected and vertex-pancyclic while containing no pancyclic edge.

What would settle it

Verification for a concrete small k, such as k=3, that the constructed graph on its stated number of vertices indeed has no edge lying in cycles of every length from 3 through n.

Figures

Figures reproduced from arXiv: 2605.21165 by Bo Zhou, Leyou Xu.

Figure 1
Figure 1. Figure 1: Illustration of the external edges through a fixed port [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graph G1. 3.1 Connectivity Lemma 2. For every positive integer k, the graph Gk is k-connected. Proof. It is enough to prove that deleting fewer than k vertices leaves a connected graph. We first claim that each layer Gk[Lr] is connected. Indeed, if x, y ∈ Q and x ̸= y, then x + y ∈ Pi for some unique i ∈ {0, 1, 2}, and so x (r) i y (r) i is an edge. Since each T (r) x is a triangle, it follows that all… view at source ↗
read the original abstract

An edge of a graph of order $n$ is pancyclic if it lies in a cycle of every length $3,\ldots,n$. A graph of order $n$ is vertex-pancyclic if every vertex lies in a cycle of every length $3,\ldots,n$. Recently, Li and Zhan proved that every $2$-connected $[4,2]$-graph of order at least seven contains a pancyclic edge. Zhan asked whether there exists a positive integer $k$ such that every $k$-connected vertex-pancyclic graph contains a pancyclic edge. We answer this question by showing that for every positive integer $k$, there is a $k$-connected vertex-pancyclic graph containing no pancyclic edge.

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

1 major / 3 minor

Summary. The manuscript proves that for every positive integer k there exists a k-connected vertex-pancyclic graph containing no pancyclic edge. This is established by explicit constructions of graph families for each k, together with verifications that the graphs are k-connected, that every vertex lies in cycles of all lengths 3 through n, and that no edge lies in cycles of all lengths 3 through n. The result supplies a negative answer to Zhan’s question (following Li and Zhan’s theorem for 2-connected [4,2]-graphs) by exhibiting, for each k, a counterexample to the forced presence of a pancyclic edge.

Significance. The explicit constructions constitute a concrete strength: they furnish falsifiable examples that can be examined directly and potentially extended. If the verifications hold, the result shows that neither k-connectivity nor vertex-pancyclicity forces the existence of a pancyclic edge, thereby clarifying the boundary between these properties and advancing the study of pancyclicity in highly connected graphs.

major comments (1)
  1. [Main construction and verification sections following the abstract] Main construction and verification sections following the abstract: the simultaneous satisfaction of k-connectivity, vertex-pancyclicity for every vertex, and the complete absence of any pancyclic edge is the load-bearing step. The manuscript must supply a self-contained argument that the chosen edge set avoids cycles of every length while still ensuring every vertex participates in cycles of every length; any gap in this joint verification would undermine the existence claim for arbitrary k.
minor comments (3)
  1. [Introduction] The abstract defines pancyclic edges and vertex-pancyclicity clearly; the introduction could add a brief sentence recalling the precise statement of Li and Zhan’s theorem to sharpen the contrast with the new result.
  2. [Construction section] Notation for the order n of the constructed graphs should be introduced uniformly when the families are defined, to avoid ambiguity when stating the cycle-length conditions.
  3. [Construction section] A short table or diagram illustrating the smallest constructed example for k=3 would improve readability without altering the proof.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for recognizing the value of our explicit constructions in providing a negative answer to Zhan's question. We address the single major comment below and have revised the manuscript to strengthen the presentation of the joint verifications.

read point-by-point responses

  1. Referee: [Main construction and verification sections following the abstract] Main construction and verification sections following the abstract: the simultaneous satisfaction of k-connectivity, vertex-pancyclicity for every vertex, and the complete absence of any pancyclic edge is the load-bearing step. The manuscript must supply a self-contained argument that the chosen edge set avoids cycles of every length while still ensuring every vertex participates in cycles of every length; any gap in this joint verification would undermine the existence claim for arbitrary k.

    Authors: We agree that a clear, self-contained joint verification is essential. The original sections establish k-connectivity via minimum-degree arguments and Menger's theorem, construct explicit cycles of all lengths through each vertex using paths in the base graph plus added vertices, and show no edge is pancyclic by exhibiting, for each edge, a specific length l where no cycle of length l exists due to the bipartite-like structure or forbidden subpaths in the construction. To address the concern directly, the revised manuscript adds an integrated subsection that cross-references these arguments in a single flow, with a table summarizing the forbidden cycle lengths per edge type and the cycle constructions per vertex. This makes the simultaneous satisfaction explicit without external dependencies and covers arbitrary k by induction on the family parameter. revision: yes

Circularity Check

0 steps flagged

Explicit construction is self-contained

full rationale

The paper proves the existence claim by constructing, for each k, a specific family of graphs that are simultaneously k-connected, vertex-pancyclic, and free of pancyclic edges. The load-bearing steps are the explicit definition of the graphs followed by direct verification of the three properties; these verifications rely on standard graph-theoretic arguments rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equation or premise reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result relies on standard definitions of graph connectivity and pancyclicity together with an explicit construction whose correctness is asserted but not inspectable from the abstract alone.

axioms (1)
  • standard math Standard definitions of k-connectivity, vertex-pancyclicity, and pancyclic edges in finite undirected graphs.
    Invoked throughout the abstract and title; these are background facts from graph theory.

pith-pipeline@v0.9.0 · 5646 in / 1149 out tokens · 24265 ms · 2026-05-21T03:23:10.852869+00:00 · methodology

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

12 extracted references · 12 canonical work pages

  1. [1]

    Bondy, Pancyclic graphs

    J.A. Bondy, Pancyclic graphs. I,J. Combin. Theory Ser. B11(1971) 80–84

    work page 1971

  2. [2]

    Bondy, A

    J.A. Bondy, A. W. Ingleton, Pancyclic graphs. II,J. Combin. Theory Ser. B20 (1976) 41–46

    work page 1976

  3. [3]

    Broersma, A note on the minimum size of a vertex pancyclic graph,Discrete Math.164(1997) 29–32

    H.J. Broersma, A note on the minimum size of a vertex pancyclic graph,Discrete Math.164(1997) 29–32

    work page 1997

  4. [4]

    Chvátal, P

    V. Chvátal, P. Erdős, A note on Hamiltonian circuits,Discrete Math.2(1972) 111–113

    work page 1972

  5. [5]

    Cream, R.J

    M. Cream, R.J. Gould, K. Hirohata, Extending vertex and edge pancyclic graphs, Graphs Combin.34(2018) 1691–1711

    work page 2018

  6. [6]

    Gould, Advances on the Hamiltonian problem: a survey,Graphs Combin.19 (2003) 7–52

    R.J. Gould, Advances on the Hamiltonian problem: a survey,Graphs Combin.19 (2003) 7–52

    work page 2003

  7. [7]

    Hendry, Extending cycles in graphs,Discrete Math.85(1990) 59–72

    G.R.T. Hendry, Extending cycles in graphs,Discrete Math.85(1990) 59–72

    work page 1990

  8. [8]

    Hobbs, The square of a block is vertex pancyclic,J

    A.M. Hobbs, The square of a block is vertex pancyclic,J. Combin. Theory Ser. B20 (1976) 1–4

    work page 1976

  9. [9]

    C. Li, X. Zhan, Every2-connected[4 , 2]-graph of order at least seven contains a pancyclic edge,Discrete Math.349(2026) 115154

    work page 2026

  10. [10]

    Randerath, I

    B. Randerath, I. Schiermeyer, M. Tewes, L. Volkmann, Vertex pancyclic graphs, Discrete Appl. Math.120(2002) 219–237

    work page 2002

  11. [11]

    Schmeichel, S.L

    E.F. Schmeichel, S.L. Hakimi, Pancyclic graphs and a conjecture of Bondy and Chvátal,J. Combin. Theory Ser. B17(1974) 22–34

    work page 1974

  12. [12]

    Zhang, D.A

    K.M. Zhang, D.A. Holton, On edge-pancyclic graphs,Soochow J. Math.19(1993) 37–41. 9

    work page 1993