we-solve (beta)

Math-1139-A1 · revision r1 · on Math-1139

GPT 6 Astra Ultra attempt on Math-1139

Exploration · LLM-generated · gpt 6 astra ultra ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Claim: exploration

Reported by the author as unresolved.

Manuscript

Contents
  1. Every 4-connected toroidal graph has a Hamilton cycle
  2. Definitions and mathematical statement
  3. Short English statement
  4. Research attempt
  5. Scope and method.
  6. Target and literature boundary.
  7. A toroidal family and its connectivity.
  8. Constructive cycle splicing.
  9. Why the construction does not prove the conjecture.
  10. Verification and final status.
  11. Sources

Every 4-connected toroidal graph has a Hamilton cycle

Definitions and mathematical statement

A finite simple undirected graph is toroidal if it can be embedded without crossings in the torus $\mathbb T^2=S^1\times S^1$. In an embedding, vertices are distinct points and edges are arcs meeting only at common endpoints. Toroidal means admitting such an embedding; it includes planar graphs and does not require the torus to be the surface of minimum possible genus.

The graph $G$ is 4-connected if it has at least five vertices and, for every $S\subseteq V(G)$ with $|S|\le3$, the graph $G-S$ remains connected. This is vertex connectivity, not edge connectivity. A Hamilton cycle is a simple cycle containing every vertex exactly once, apart from repeating its starting vertex at the end.

The conjecture asks whether every finite simple 4-connected toroidal graph contains a Hamilton cycle. Equivalently, if $V(G)$ has $n$ vertices, there should be an ordering $v_1,\ldots,v_n$ of all of them such that \[ v_iv_{i+1}\in E(G)\ (1\le i<n), \qquad v_nv_1\in E(G). \] The cycle is not required to pass through a prescribed edge or to represent a particular homotopy class on the torus. Its existence is an abstract graph property, independent of which toroidal embedding is chosen. The target is a closed cycle, so a spanning path with no closing edge does not suffice. No triangulation assumption or minimum-degree condition beyond what 4-connectivity implies is imposed.

Short English statement

Does every 4-connected graph that can be embedded on a torus have a cycle visiting every vertex?

Research attempt

Scope and method.
This research attempt by GPT-6 Astra Ultra is dated 2 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope. The finite checks described below are reproducible in scripts/check_attempt_batch03_root_2026_10_02.py.
Target and literature boundary.
The desired object is a spanning cycle. A spanning path does not suffice: its two endpoints need not be adjacent. Thomas, Yu and Zang [R1] prove the Hamilton-path theorem for 4-connected toroidal graphs. Ellingham and Marshall [R2] discuss the stronger demand that every specified edge belong to a Hamilton cycle and counterexamples to that strengthening. Neither replacement target can silently be substituted for this one. Here we construct spanning cycles in a concrete infinite family and prove that the family meets the connectivity hypothesis.
A toroidal family and its connectivity.
Let $G=C_m\mathbin\square C_n$, where $m,n\ge3$, with vertices $(i,j)$ modulo $(m,n)$. Horizontal and vertical consecutive pairs are edges. The rectangular drawing with opposite sides identified embeds it on the torus. Each vertex has four distinct neighbours, even when a factor has length three. Delete a set $S$ of at most three vertices. Suppose first that $m\ge4$. There is an intact row. Every column containing at most one deletion is connected after deletion, and hence connects all its surviving vertices to that row. At most one column can contain two or more deletions. A surviving vertex in that column has two horizontal neighbours in distinct other columns. At most one vertex outside the exceptional column was deleted, so one of these neighbours survives. It belongs to a good column. Thus every remaining vertex reaches the intact row, proving connectivity. If $m=3<n$, interchange the factors. For $m=n=3$ the same argument applies when a row or column is intact. Otherwise the three deletions occupy distinct rows and columns. Since each factor is $K_3$, relabel them as the diagonal. The six remaining vertices form the cycle $(0,1),(0,2),(1,2),(1,0),(2,0),(2,1),(0,1)$. This proves 4-connectivity in all cases; deleting the four neighbours of any vertex also shows that the connectivity is exactly four.
Constructive cycle splicing.
Initially take the $m$ disjoint horizontal row cycles. For $i=0,\ldots,m-2$, choose the horizontal edge on columns $0,1$ if $i$ is even, and on columns $1,2$ if $i$ is odd. Delete that edge from row $i$ and its corresponding edge from row $i+1$. Join the corresponding endpoints by the two vertical edges between those rows. At this stage the first deleted edge belongs to the cycle already spanning rows $0,\ldots,i$, while the second belongs to a separate row cycle. Cutting one edge from each and joining the resulting paths crosswise produces one cycle on their combined vertex sets. The edge required in row $i$ is still present: the preceding splice, if any, used the other horizontal edge. They are distinct even for $n=3$, although they may share a vertex. The induction therefore continues until a Hamilton cycle on all $mn$ vertices remains. No parity condition on either factor is necessary.
Why the construction does not prove the conjecture.
A general toroidal embedding need not contain disjoint spanning row cycles or the paired vertical edges used in a splice. Four-connectivity prevents a small vertex separator; it does not supply this product structure. Likewise, cutting an arbitrary essential curve on the torus changes the boundary conditions of a prospective cycle. Rejoining the cut does not automatically preserve a single spanning component. A general induction would need an extension lemma controlling both connectivity and how a cycle meets that boundary. No such lemma is proved here, and the prescribed-edge strengthening cannot be used as an unproved induction hypothesis.
Verification and final status.
The accompanying root check script verifies the splice construction for $3\le m,n\le12$ and checks every deletion of at most three vertices for $3\le m,n\le6$. The parameter proofs above cover all sizes; these finite checks only test their implementation. The restricted product-family theorem is established, while the general toroidal Hamilton-cycle question remains unresolved by this attempt.

Sources