Hamilton decomposition of prisms over 3-connected cubic planar graphs

Hamilton decomposition of prisms over 3-connected cubic planar graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple $3$-connected cubic planar graph. Thus every vertex has degree three, $G$ has a crossing-free drawing in the plane, and deletion of any two vertices leaves it connected. Define its prism $P=G\square K_2$ on vertex set $V\times\{0,1\}$. For each $uv\in E$ and $i\in\{0,1\}$ put an edge $(u,i)(v,i)$ in $P$, and for each $v\in V$ put the vertical edge $(v,0)(v,1)$ in $P$.

The prism is a $4$-regular graph with $2|V|$ vertices. A Hamilton decomposition into two cycles means Hamilton cycles $C_1,C_2$ in $P$ such that \[ E(P)=E(C_1)\mathbin{\dot\cup}E(C_2). \] Each cycle must visit all vertices of both layers, and each prism edge must be used exactly once by the pair.

The conjecture is that every base graph $G$ satisfying the stated hypotheses has such a decomposition. Equivalently, one seeks a Hamilton cycle $C$ of $P$ whose edge complement $(V(P),E(P)\setminus E(C))$ is connected. That complement automatically has degree two at every vertex; connectivity is what makes it one Hamilton cycle instead of several disjoint cycles. The complement is taken in the prism $P$, not in the base graph $G$. A Hamilton cycle in each layer separately would not satisfy the spanning requirement.

Short English statement

Can the prism over every 3-connected cubic planar graph be partitioned into two Hamilton cycles?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Literature and strategy.

The original entry [S2] distinguishes Hamiltonicity of a prism from decomposition into two Hamilton cycles, and attributes the decomposition question to Alspach and Rosenfeld. Its cited Hamiltonicity result cannot supply the second cycle automatically. We audit the most direct construction on the already restricted class of Hamiltonian cubic base graphs. All edges below belong to the prism, including its vertical edges; taking the complement in the base graph would change the question.

Splicing two copies of a Hamilton cycle.

Let $G$ be a simple cubic graph on $n$ vertices, with a Hamilton cycle $H$. The unused edges $M=E(G)\setminus E(H)$ form a perfect matching: precisely one edge remains at every vertex. Write $x_0,x_1$ for the copies of $x$ in $P=G\square K_2$. Choose $uv\in E(H)$. In the two layer cycles remove $u_0v_0,u_1v_1$, and add the vertical edges $u_0u_1,v_0v_1$. Call the resulting edge set $C$.

Each broken layer is a spanning $u_j$--$v_j$ path. Traversing the first path, crossing at $v$, traversing the other backwards, and crossing at $u$ visits every prism vertex once. Thus $C$ really is a Hamilton cycle; no Hamiltonicity assumption beyond that of the chosen base cycle has entered.

Exact obstruction in the complement.

Before this splice, the complement of the two layer cycles consists, for every matching edge $xy\in M$, of the square \[ x_0y_0y_1x_1x_0. \] These $n/2$ squares are disjoint and cover the prism vertices. Passing to $E(P)\setminus C$ removes the two vertical edges at $u,v$ and adds the two layer copies of $uv$. Since $uv\notin M$ and the base graph is simple, $u$ and $v$ lie in different matching edges, say $uu'$ and $vv'$. The four vertices $u,u',v,v'$ are distinct. Removing the indicated vertical edge from each corresponding square makes two paths. The added edges $u_0v_0,u_1v_1$ join them into one eight-vertex cycle. Every other square stays untouched.

Consequently the complement is a spanning 2-factor with exactly \[ 1+(n/2-2)=n/2-1 \] components. It is Hamiltonian precisely when $n=4$. For $n\ge6$, the splice gives a Hamilton cycle whose complement is demonstrably disconnected. This proves failure of this particular attack on every larger Hamiltonian cubic base, rather than merely failure in an isolated test graph. It does not disprove the conjecture, since a different Hamilton cycle could have a connected complement.

A complete smallest certificate.

For $G=K_4$, use vertex names $0,1,2,3$ and $H=01230$. The following cyclic vertex lists give a decomposition of its prism: \[ \begin{split} C_1&=(0_0,3_0,2_0,1_0,1_1,2_1,3_1,0_1),\\ C_2&=(0_0,1_0,3_0,3_1,1_1,0_1,2_1,2_0). \end{split} \] Consecutive vertices, including the last and first, are adjacent; each list has all eight vertices; their edge sets are disjoint. Since the prism has sixteen edges, they exhaust it. This covers a base satisfying all the required hypotheses: $K_4$ is simple, cubic, planar, and 3-connected.

Verification and next obstruction.

The companion script scripts/check_attempt_batch02_graphs_2026_10_01.py verifies these two cycles directly and tests the component formula on Hamiltonian circular ladders. The formula itself is proved above for every simple cubic Hamiltonian base, independently of those examples. A local modification that merges two cycles of the complementary 2-factor can also split $C$; a valid next step must keep both factors connected simultaneously. Moreover, general 3-connected cubic planar bases need not come with a Hamilton cycle, so the starting assumption would also need removal.

Final status.

The $K_4$ case and a uniform obstruction to the single-splice construction are established. Neither arbitrary Hamiltonian bases nor all bases in the catalogue are resolved. The full decomposition statement is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3178 (OPG-47356), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Hamilton decomposition of prisms over 3-connected cubic planar graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/decomposing_the_prism_of_a_3_connected_cubic_planar_graphs_in_hamilton_cycles.