gpt 6 astra ultra attempt on Math-1074

r-regular graphs are not uniquely hamiltonian.

Definitions and mathematical statement

Let $r\geq3$ be an integer and let $G=(V,E)$ be a finite simple undirected $r$-regular graph: every vertex has exactly $r$ neighbours. A Hamilton cycle is a connected spanning $2$-regular subgraph, equivalently a cycle passing through all vertices once. Count Hamilton cycles by their edge sets. Changing the starting vertex or reversing the direction of traversal does not create a new cycle.

The graph is uniquely Hamiltonian when it has exactly one Hamilton cycle. The conjecture asserts that no finite simple $r$-regular graph is uniquely Hamiltonian for any $r>2$. Writing $h(G)$ for the number of Hamilton cycles, its target is \[ h(G)\neq1\qquad \text{for every finite simple regular graph of degree }r\geq3. \] Equivalently, whenever such a $G$ has a Hamilton cycle $C$, there must be another Hamilton cycle $C'$ with $E(C')\neq E(C)$.

The assertion permits graphs with no Hamilton cycle; it does not assert that regularity alone guarantees one. The two cycles may share vertices and edges and need not be edge-disjoint. No connectivity assumption beyond that forced by existence of the first Hamilton cycle is needed. Simplicity is essential to the intended source question: parallel edges are excluded, as emphasized in its discussion. Degree two is omitted because a connected simple cycle is itself a uniquely Hamiltonian $2$-regular graph.

Short English statement

Must every Hamiltonian regular simple graph of degree greater than two have at least two distinct Hamilton cycles?

Research attempt: parity for odd degrees and a reduction to degree four

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. Hamilton cycles are counted as undirected edge sets. The task is to exclude exactly one, not to prove that a regular graph is Hamiltonian. Thomason's parity theorem [S3] settles the odd-degree case. We give the path-rotation argument explicitly and then prove that a resolution for simple four-regular graphs would settle every remaining even degree. These are established reductions recovered here, not new solutions.

1. A finite auxiliary graph of Hamilton paths.

Suppose every vertex of $G$ has odd degree, and fix an edge $ab$. Form an auxiliary graph whose vertices are all ordered Hamilton paths \[ P=(v_1,v_2,\ldots,v_n),\qquad v_1=a,\ v_2=b. \] If the final vertex $z=v_n$ is adjacent to $v_i$ for $2\le i\le n-2$, rotate the final segment to obtain \[ P'=(v_1,\ldots,v_i,v_n,v_{n-1},\ldots,v_{i+1}). \] This remains a Hamilton path with the fixed initial edge. The move is reversible, using the removed edge $v_iv_{i+1}$, and distinct choices of $i$ give distinct neighbours. There are no loops. Its degree at $P$ is therefore \[ d_{\rm aux}(P)=\deg_G(z)-1-\mathbf1_{\{za\in E(G)\}}. \] The subtracted one accounts for the predecessor of $z$; adjacency to $a$ cannot be used because rotations must preserve the initial edge. Every other neighbour is eligible.

Since $\deg_G(z)$ is odd, the auxiliary degree is odd precisely when $za$ is an edge. The handshaking lemma says that the number of odd-degree vertices of this finite auxiliary graph is even. Closing such a path with $za$ gives a Hamilton cycle containing $ab$. Conversely, orienting any Hamilton cycle containing $ab$ to begin $a,b$ and removing its final edge to $a$ gives exactly one such ordered path. Hence the number of Hamilton cycles containing $ab$ is even. If a Hamilton cycle exists, choose $ab$ on it; the count is positive and even, so a second edge-distinct cycle exists. This proves the conjecture for every odd regular degree, and indeed for all graphs with every degree odd.

2. Reducing all even degrees to four.

Let $G$ be simple, $r$-regular with even $r\ge4$, and let $C$ be a Hamilton cycle. Its edge complement $R=G-E(C)$ is $(r-2)$-regular. We show it has a spanning two-factor. Orient an Euler tour of each connected component of $R$. Every vertex then has indegree and outdegree $d=(r-2)/2\ge1$.

Make a bipartite graph with a left and right copy of every vertex, and an edge from the left copy of $u$ to the right copy of $v$ for each directed edge $u\to v$. This graph is $d$-regular on both sides. Counting edges from any left subset proves Hall's inequality, so it has a perfect matching. The selected directed edges give one incoming and one outgoing edge at each original vertex, hence a disjoint union of directed cycles spanning $V(G)$. No loop exists, and a directed two-cycle would require both orientations of one original simple edge, which were not included. Forgetting orientations therefore gives an ordinary spanning two-factor $F\subseteq R$.

The union $C\cup F$ is a simple four-regular spanning subgraph of $G$. A second Hamilton cycle there would also be a second Hamilton cycle in $G$. Thus the four-regular case is sufficient for every even regular degree. Together with the parity proof, it suffices for the entire canonical question.

Verification and the exact parity barrier.

For even original degrees, the displayed auxiliary-degree formula makes closing paths have even auxiliary degree and nonclosing paths odd. The handshaking lemma then controls the wrong class of paths; it no longer forces a second Hamilton cycle. This is a precise failure of extending the same parity argument, not a counterexample. The script [S4] checks Hamilton-cycle counts through one fixed edge of $K_4$ and $K_6$, obtaining two and twenty-four respectively. Those small counts illustrate the odd-degree theorem but do not address the missing four-regular case.

Final status

UNRESOLVED. The odd-degree parity theorem is proved and the remaining regular cases are reduced to degree four. The four-regular case is not resolved. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3167 (OPG-480), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, r-regular 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/uniquely_hamiltonian_graphs.
• S3 A. G. Thomason, Hamiltonian Cycles and Uniquely Edge Colourable Graphs, Annals of Discrete Mathematics 3 $1978$, 259--268. Author-hosted paper checked 1 October 2026. https://www.dpmms.cam.ac.uk/~agt2/HC.pdf.
• S4 GPT-6 Astra Ultra, finite Hamilton-cycle count checks, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.