Every prism over a 3-connected planar graph is hamiltonian.

Medium ★★ Graph Theory » Basic Graph Theory » Cycles

Authors: Kaiser, Tomás, Král, Daniel, Rosenfeld, Moshe, Ryjácek, Zdenek, Voss, Heinz-Jürgen— posted by fhavet on 2013-03-11

Status disproved high confidence

The conjecture was disproved by Simon Špacapan, who constructed a 3-connected planar graph whose prism over $K_2$ is not Hamiltonian (arXiv 2019; published in J. Combin. Theory Ser. B, 2021). Subsequent work by Špacapan (J. Graph Theory, 2024) shows that any counterexample must contain cubic vertices: every 3-connected planar graph of minimum degree at least 4 is prism-Hamiltonian.

Cited literature (2)

counterexample A counterexample to prism-hamiltonicity of 3-connected planar graphs (2019)

Simon Špacapan · arXiv preprint (later in J. Combin. Theory Ser. B) · arXiv:1906.06683 · doi:10.1016/j.jctb.2020.10.003

Constructs a 3-connected planar graph whose prism is not Hamiltonian, disproving the Rosenfeld-Barnette/Kaiser-Král-Rosenfeld-Ryjáček-Voss conjecture.
partial Polyhedra without cubic vertices are prism-hamiltonian (2021)

Simon Špacapan · arXiv preprint (later in J. Graph Theory, 2024) · arXiv:2104.04266 · doi:10.1002/jgt.23078

Proves that every 3-connected planar graph with minimum degree at least 4 is prism-Hamiltonian, showing counterexamples must contain cubic vertices.

Reviewer notes. The ScienceDirect (J. Combin. Theory Ser. B) and Wiley (J. Graph Theory) publisher pages returned HTTP 403, so the canonical journal URLs could not be fetched. Verification was performed via the arXiv abstract pages, which match the same titles/authors/abstracts; the DOIs listed are the standard ones reported in search results but were not directly fetched. The 2019 arXiv paper is the original counterexample announcement and the journal version appeared in J. Combin. Theory Ser. B (2021).

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Conjecture. If $ G $ is a $ 3 $ -connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Discussion

The Cartesian product $ G\square K_2 $ is called the prism over $ G $ . Rosenfeld and Barnette [RB] showed that the Four-Colour Theorem implies that cubic planar 3-connected graphs have hamiltonian prisms. Fleischner [F] found a proof avoiding the use of the Four Colour Theorem. Eventually, Paulraja [P] showed that planarity is inessential here : The prism over any 3-connected cubic graph has a Hamilton cycle. Clearly, if $ G $ is hamiltonian, then $ G\square K_2 $ is also hamiltonian. A classical theorem of Tutte [T] states that all 4-connected planar graphs are hamiltonian. There are well-known examples of non-hamiltonian 3-connected planar graphs.

Bibliography

[F] H. Fleischner, The prism of a 2-connected, planar, cubic graph is hamiltonian (a proof independent of the four colour theorem), in Graph theory in memory of G. A. Dirac, Volume 41 of Ann. Discrete Math., 1989), 141–170.
★ [KKRRV] T. Kaiser, D. Kráľ, M. Rosenfeld, Z. Ryjáček, H.-J. Voss, Hamilton cycles in prisms, Journal of graph theory 56 (2007), 249-269.
[P] P. Paulraja, “A characterization of hamiltonian prisms”, J. Graph Theory 17 (1993) 161–171.
[RB] M. Rosenfeld and D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5 (1973) 389–394.
[T] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116.