Hamiltonian cycles in line graphs of infinite graphs

Definitions and mathematical statement

Let $G$ be a connected locally finite simple graph, finite or infinite. Its line graph $L(G)$ has one vertex for each edge of $G$, with two distinct vertices adjacent exactly when the corresponding edges have a common endpoint. Local finiteness of $G$ ensures local finiteness of $L(G)$.

For an infinite locally finite graph $H$, an end is an equivalence class of rays, where two rays are equivalent if their tails lie in the same component after every finite vertex deletion. Its Freudenthal compactification $|H|$ adds these ends to the geometric graph; neighborhoods of an end follow the component containing its rays outside a finite vertex set, together with the incident edge tails and ends in that component. A Hamilton circle is a subspace homeomorphic to $S^1$ containing every vertex of $H$. For a finite graph this is an ordinary Hamilton cycle.

The two conjectures are:

1. If $G$ is four-edge-connected, then $L(G)$ has a Hamilton circle.
2. If $L(G)$ is four-vertex-connected, then $L(G)$ has a Hamilton circle.

Four-edge-connected means that deleting fewer than four edges cannot disconnect $G$. Four-vertex-connected means that the line graph has at least five vertices and deleting fewer than four vertices cannot disconnect it.

The conclusions concern the compactification of the line graph, not of the original graph. A spanning double ray is not the definition in general: Hamilton circles can have a more complicated trace in graphs with several ends. Both assertions quantify over all locally finite graphs satisfying their respective connectivity condition.

Short English statement

Do four-edge-connectivity of a locally finite graph, or four-vertex-connectivity of its line graph, force a Hamilton circle in the line graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3300 (OPG-488), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Hamiltonian cycles in line graphs of infinite graphs. Original problem and discussion. http://www.openproblemgarden.org/op/hamiltonian_cycles_in_line_graphs_of_infinite_graphs.
• S3 B. Mohar, Hamiltonicity of infinite graphs, including the line-graph questions. https://www.fmf.uni-lj.si/~mohar/Problems/P0703_HamiltonicityInfinite.html.