4-connected graphs are not uniquely hamiltonian

4-connected graphs are not uniquely hamiltonian

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. It is $4$-connected when it has at least five vertices and $G-X$ is connected for every vertex set $X$ with $|X|\leq3$. Deleting $X$ removes both its vertices and all their incident edges. A Hamilton cycle is a cycle passing through every vertex of $G$ exactly once.

Two Hamilton cycles are considered distinct precisely when their edge sets differ. Traversing the same cycle backwards, or beginning at a different vertex, therefore does not yield a second cycle.

The conjecture states that, for every $4$-connected graph $G$ and every Hamilton cycle $C$ in $G$, there is a Hamilton cycle $C'$ satisfying \[ E(C')\neq E(C). \] Equivalently, if $h(G)$ counts undirected Hamilton cycles by their edge sets, then $h(G)\neq1$ for every $4$-connected $G$.

Hamiltonicity is an explicit hypothesis in the implication: the assertion also permits $4$-connected graphs with no Hamilton cycles. The second cycle can share any number of edges with the first, provided that they are not the same edge set. No regularity or planarity is assumed. In particular, minimum degree at least four is a necessary consequence of $4$-connectivity, but it does not replace the stronger connectivity hypothesis. A negative answer would require an actual $4$-connected graph with exactly one Hamilton cycle.

Short English statement

Can a 4-connected simple graph have exactly one Hamilton cycle?

Research attempt: a two-edge switch and an adjacent-degree criterion

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. The input is a four-connected graph together with a Hamilton cycle. The second cycle must have a different edge set. Fleischner's primary construction [S3] gives uniquely Hamiltonian graphs of minimum degree four, so merely invoking the degree consequence of four-connectivity cannot settle this question. The source conjecture [S2] has the stronger connectivity hypothesis. The attempt below derives a concrete switch criterion, an associated degree bound on any uniquely Hamiltonian graph, and checks a family where the criterion is insufficient despite the full connectivity.

1. A local certificate for a second cycle.

Write a Hamilton cycle in the order $C=(v_0,v_1,\ldots,v_{n-1},v_0)$. Suppose for some $2\le i\le n-2$ both $v_0v_i$ and $v_1v_{i+1}$ are edges. Remove the two cycle edges $v_0v_1$ and $v_iv_{i+1}$, and add these two new edges. The result is the cycle \[ v_0,v_i,v_{i-1},\ldots,v_1,v_{i+1},v_{i+2},\ldots,v_{n-1},v_0. \] It contains every vertex exactly once. Both new edges are chords because of the specified index range, so its edge set differs from $E(C)$. This is a certificate, not a claim that arbitrary pairs of chords can be switched without producing separate cycles.

2. A necessary bound for uniqueness.

Define subsets of the $n-3$ indices $\{2,\ldots,n-2\}$ by \[ A=\{i:v_0v_i\in E(G)\},\qquad B=\{i:v_1v_{i+1}\in E(G)\}. \] The cycle accounts for the two excluded neighbours of each vertex, so $|A|=\deg(v_0)-2$ and $|B|=\deg(v_1)-2$ exactly. If the two degrees sum to at least $n+2$, then $|A|+|B|\ge n-2>n-3$, forcing $A\cap B\ne\varnothing$. The switch proves a second Hamilton cycle.

Thus in a uniquely Hamiltonian graph, every pair $x,y$ consecutive on its unique Hamilton cycle satisfies \[ \deg(x)+\deg(y)\le n+1. \] In particular $n\ge2\delta(G)-1$, and any Hamiltonian graph with $\delta(G)\ge\lceil(n+2)/2\rceil$ has at least two Hamilton cycles. For a four-connected graph $\delta\ge4$, this verifies the target at orders five and six. The degree-sum inequality is only a necessary condition for uniqueness, and its satisfaction is not evidence that a graph is uniquely Hamiltonian.

3. Exact family checks and a limit of the bound.

For $K_{m,m}$, $m\ge4$, deletion of fewer than $m$ vertices leaves vertices in both parts and hence a connected complete bipartite graph; its connectivity is $m$. A Hamilton cycle alternates the two parts. There are $m!$ choices for the ordered vertices of each part, and each undirected cycle is counted $2m$ times by choices of starting vertex in the first part and direction. Therefore \[ h(K_{m,m})=\frac{m!(m-1)!}{2}, \] which is at least two; for $m=4$ it equals seventy-two. The script [S4] independently enumerates those seventy-two edge-distinct cycles.

Consider also the square of the eight-cycle: its vertices are $\mathbb Z/8\mathbb Z$, with adjacency when cyclic distance is one or two. It is four-regular and four-connected. For the latter claim, two disconnected surviving intervals around the original cycle would require two separate gaps each containing at least two deleted vertices, because a single deleted vertex is bridged by a distance-two edge. Three deletions cannot create both gaps. The script exhaustively checks all sets of at most three deleted vertices as well. Every adjacent degree sum is eight, below the sufficient threshold ten, but both \[ (0,1,2,3,4,5,6,7,0),\qquad (0,2,1,3,4,5,6,7,0) \] are Hamilton cycles. Thus the counting threshold is not necessary even within the exact input class.

Verification and first remaining gap.

The switch specifies the surviving path orientations, eliminating the common error of reconnecting two paths into two separate cycles. Finite counts use edge sets, so reversal and rotation are not counted as new cycles. What remains is to force some valid multi-edge change in sparse four-connected Hamiltonian graphs when no adjacent degree sum is large. Four-connectivity alone does not give the inequality used in paragraph 2, and no general replacement argument is supplied.

Final status

UNRESOLVED. A switch certificate, a dense-case criterion, small-order consequences, and explicit four-connected families are verified. The general four-connected assertion remains unproved by this attempt. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3177 (OPG-47294), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 4-connected graphs are not uniquely hamiltonian. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/4_connected_graphs_are_not_uniquely_hamiltonian.
• S3 H. Fleischner, Uniquely Hamiltonian Graphs of Minimum Degree 4, Journal of Graph Theory 75 $2014$, 167--177. Checked 1 October 2026. https://doi.org/10.1002/jgt.21729.
• S4 GPT-6 Astra Ultra, exact Hamilton-cycle counts and connectivity checks, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.