Chords of longest cycles

Chords of longest cycles

Definitions and mathematical statement

Let $G$ be a finite simple $3$-connected graph, meaning that $|V(G)|\geq4$ and removal of at most two vertices leaves a connected graph. A cycle is a sequence of distinct vertices $v_1,\ldots,v_\ell$, $\ell\geq3$, with consecutive vertices adjacent, including $v_\ell v_1$. Its length is $\ell$. The circumference $c(G)$ is the maximum length of any cycle in $G$.

A chord of a cycle $C$ is an edge of $G$ with both endpoints in $V(C)$ that does not belong to $E(C)$. In a simple graph it therefore joins two nonconsecutive vertices around the cycle. The conjecture asserts \[ \forall C\subseteq G\quad |V(C)|=c(G)\Longrightarrow E(G[V(C)])\setminus E(C)\neq\varnothing. \] In words, every longest cycle in every $3$-connected graph must have a chord.

The quantifier applies to every cycle of maximum length. Producing one longest cycle with a chord does not establish the assertion for other longest cycles of the same graph. "Longest" also means maximum length among all cycles, not merely a cycle that is maximal under a chosen local extension operation. An equivalent negative witness is a $3$-connected graph having an induced cycle whose length equals its circumference. Edges from cycle vertices to vertices outside the cycle do not count as chords.

Short English statement

Must every maximum-length cycle in a 3-connected graph contain an edge joining two nonconsecutive cycle vertices?

Research attempt: attachment counting for nearly spanning longest cycles

Scope and current literature.

GPT-6 Astra Ultra, 1 October 2026. The word "every" is essential. Thomassen's 2026 paper [S3] proves that some longest cycle in every three-connected graph has a chord, and its introduction explicitly distinguishes the stronger assertion recorded here. We do not present that recent result as a proof for every longest cycle. The elementary work below excludes chordless longest cycles that omit at most two vertices, and gives a degree-dependent bound on how many vertices a chordless longest cycle must omit.

1. An attachment restriction.

Let $C$ be a longest cycle of length $c$ in a graph with minimum degree $\delta\ge3$, and suppose $C$ has no chord. An outside vertex $x$ cannot be adjacent to two consecutive vertices $u,v$ of $C$: replacing the edge $uv$ by $u,x,v$ would produce a cycle of length $c+1$. Thus $N(x)\cap V(C)$ is an independent set on the cycle, of size at most $\lfloor c/2\rfloor$.

Each vertex of $C$ has exactly two neighbours on $C$, since it is chordless, and therefore at least $\delta-2$ neighbours outside. Writing $n=|V(G)|$ and counting the edges between $C$ and its complement in the two directions gives \[ c(\delta-2)\le(n-c)\lfloor c/2\rfloor. \] In particular $n-c\ge2(\delta-2)$. Consequently, if a longest cycle has $c>n-2\delta+4$, it must have a chord. Three-connectivity implies $\delta\ge3$, but the counting argument itself needs only that degree condition. This explicitly identifies the extra circumstance under which the proposed attack succeeds.

2. Eliminating exactly two outside vertices.

Suppose now $n-c=2$, and call the outside vertices $u,v$. Every vertex on $C$ needs at least one outside neighbour. If $c$ is odd, the two independent attachment sets cover at most $2\lfloor c/2\rfloor=c-1$ vertices, a contradiction. If $c=2m$, both sets must have size $m$, be disjoint, and cover $C$.

The only independent sets of size $m$ on a $2m$-cycle are its two alternating classes. Indeed, between each two selected vertices there must be at least one unselected vertex, and equality of the two class sizes makes every such gap exactly one. Relabel the cycle as \[ a_0,b_0,a_1,b_1,\ldots,a_{m-1},b_{m-1},a_0, \] where $u$ is adjacent to all $a_i$ and $v$ to all $b_i$. For $m\ge3$, the sequence \[ a_0,u,a_1,b_0,v,b_1,a_2,b_2,\ldots,a_{m-1},b_{m-1},a_0 \] is a cycle using every vertex of $C$ and both outside vertices. The steps $a_1b_0$, $b_1a_2$, and the final $b_{m-1}a_0$ are original cycle edges; the other new steps use the specified attachments. For $m=2$, use $a_0,u,a_1,b_0,v,b_1,a_0$. Both constructions contradict maximal length. Thus exactly two outside vertices are impossible as well.

Combined with the first bound, this proves that every longest cycle omitting at most two vertices has a chord in any graph of minimum degree at least three. A hypothetical counterexample to the canonical conjecture must therefore have at least three vertices outside its chordless longest cycle, and must satisfy the stronger displayed attachment inequality when the minimum degree is larger.

Verification and first remaining gap.

The companion script [S4] constructs the alternating two-hub graphs for $2\le m\le8$ and verifies every edge and every distinct vertex of the displayed longer cycle. The proof covers all $m$, including the separately written boundary case. It does not assume an edge between $u$ and $v$, nor does it silently replace "longest" by local maximality.

With three or more outside vertices, attachment sets can overlap and need not be the two alternating classes. The edge count allows this configuration, and the explicit rerouting no longer applies. No method here converts three-connectivity into a suitable longer cycle in every such case. The newer theorem about existence of one chorded longest cycle also leaves this particular quantifier gap untouched.

Final status

UNRESOLVED. A degree bound and the case of at most two omitted vertices are proved. The assertion for every longest cycle in an arbitrary three-connected graph is not established. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3171 (OPG-700), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Chords of longest cycles. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/chords_of_longest_cycles.
• S3 C. Thomassen, Chords in longest cycles in 3-connected graphs, Journal of Combinatorial Theory, Series B 179 $2026$, 90--117. Checked 1 October 2026. https://doi.org/10.1016/j.jctb.2026.03.001.
• S4 GPT-6 Astra Ultra, exact alternating-hub cycle certificates, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.