Hamiltonian cycles in line graphs

Hamiltonian cycles in line graphs

Definitions and mathematical statement

For a finite simple undirected graph $H$, the line graph $L(H)$ has vertex set $E(H)$. Distinct edges of $H$ become adjacent vertices of $L(H)$ exactly when they share an endpoint. A graph $G$ is a line graph if it is isomorphic to $L(H)$ for some finite simple graph $H$.

A graph is $4$-connected if it has at least five vertices and remains connected after deletion of any set of at most three vertices. A Hamilton cycle is a connected spanning subgraph of degree two at every vertex, hence a simple cycle visiting the entire graph.

The conjecture states that every $4$-connected line graph has a Hamilton cycle. In terms of a root graph $H$, whenever $L(H)$ is $4$-connected there should be a cyclic ordering \[ e_1,e_2,\ldots,e_m\qquad(m=|E(H)|) \] of all edges of $H$ such that $e_i$ and $e_{i+1}$ share an endpoint for every index modulo $m$.

This ordering is the Hamilton cycle in $L(H)$. It need not be an Euler tour in $H$: consecutively shared endpoints need not give a consistent traversal of each original edge. The hypothesis concerns vertex deletion in the line graph, not vertex connectivity of $H$. In particular, it should not be replaced by the different assumption that the root graph itself is $4$-edge-connected. The root graph is useful for expressing the target, but the conjecture is a property of $G=L(H)$.

Short English statement

Does every line graph that remains connected after deletion of any three vertices contain a Hamilton cycle?

Research attempt: an exact translation to a dominating Eulerian subgraph

Scope, literature, and plan.

GPT-6 Astra Ultra, 1 October 2026. Four-connectivity is imposed on $L(H)$, not on the root $H$. Harary and Nash-Williams [S3] supply the classical dominating Eulerian characterization; the argument is reproduced below to expose the actual missing step. Kaiser and Vrána [S4] prove Hamiltonicity for five-connected line graphs of minimum degree at least six. That stronger hypothesis cannot simply replace the present one, and no claim that it is the latest optimal partial result is needed here.

1. A sufficient certificate in the root graph.

Call a connected even-degree subgraph $D$ of $H$ dominating when every edge of $H$ has at least one endpoint in $V(D)$. Allow $D$ to be a single vertex without edges. Assume $|E(H)|\ge3$. If $D$ has edges, follow an Euler tour of $D$, listing its edges cyclically. For each edge outside $D$, choose one endpoint in $V(D)$ and assign the edge to it. At one visit to each such vertex $v$ in the tour, insert all edges assigned to $v$ between the incoming and outgoing tour edges, in any order.

This cyclic list contains every edge of $H$ exactly once. Consecutive edges share an endpoint: inside each inserted block they all meet $v$, and the two adjacent tour edges also meet $v$. Thus it is a Hamilton cycle in $L(H)$. If $D$ is a single vertex, domination means every edge of $H$ meets that vertex, and any cyclic ordering of those edges works. The certificate requires no spanning Euler tour of the whole root graph.

2. Recovering that certificate from a line-graph cycle.

Conversely, let $e_1,\ldots,e_m$ be a Hamilton cyclic ordering in $L(H)$. For each $i$, let $v_i$ be the common endpoint of $e_i$ and $e_{i+1}$, with indices taken modulo $m$. The endpoint is unique because $H$ is simple and the two edges are distinct. Both $v_{i-1}$ and $v_i$ are endpoints of $e_i$.

When $v_{i-1}\ne v_i$, traverse $e_i$ from the former to the latter. When they agree, omit $e_i$ from this traversal and stay at the shared vertex. Omitting these stationary steps leaves a closed trail whose used edges are all distinct. If any edge is used, its edge set $D$ is connected and has even degrees, because arrivals and departures pair at every vertex. Every omitted edge meets a vertex of the trail: along each stationary block the common vertex equals the endpoint of its neighbouring nonstationary block. Thus $D$ is dominating. If no edge is used, all $v_i$ agree, and their one common vertex is the degenerate dominating certificate. This proves the equivalence in both directions.

3. Translating connectivity without strengthening it.

Deleting at most three vertices of $L(H)$ corresponds to deleting at most three edges of $H$. The remaining line graph is disconnected exactly when the remaining root graph has at least two components each containing an edge. Isolated root vertices produce no line-graph vertices and must be ignored. Hence the hypothesis forbids small edge separations into two edge-containing parts, rather than all small edge cuts in the usual sense.

For example $H=K_{1,5}$ has bridges and vertices of odd degree, yet $L(H)=K_5$ is four-connected and Hamiltonian. Its central vertex is the degenerate dominating certificate. The script [S5] explicitly checks the line-graph construction and its connectivity. This example rules out replacing the desired certificate by a spanning even-degree subgraph of the root: no such nontrivial spanning subgraph exists in a star, though the original target holds.

Verification and first remaining gap.

In the sufficiency proof every unused edge is assigned once, even if both endpoints lie in $D$; no edge is duplicated by insertion. In the converse, stationary steps are necessary: consecutive line-graph adjacencies do not in general orient all root edges into an Euler tour. The unresolved assertion is that the stated prohibition on small edge separations always yields a dominating connected even subgraph, possibly a single vertex. The equivalence identifies the correct target but does not construct it from four-connectivity.

Final status

UNRESOLVED. The dominating Eulerian characterization is proved and the connectivity translation is checked. No general construction at the four-connected threshold is established. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3168 (OPG-485), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Hamiltonian cycles in line graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/hamiltonian_cycles_in_line_graphs.
• S3 F. Harary and C. St. J. A. Nash-Williams, On Eulerian and Hamiltonian Graphs and Line Graphs, Canadian Mathematical Bulletin 8 $1965$, 701--709. Checked 1 October 2026. https://doi.org/10.4153/CMB-1965-051-3.
• S4 T. Kaiser and P. Vrána, Hamilton cycles in 5-connected line graphs, arXiv:1009.3754, revised 2011. Checked 1 October 2026. https://arxiv.org/abs/1009.3754.
• S5 GPT-6 Astra Ultra, exact line-graph example check, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.