Every graph occurs as an induced subgraph of some hypohamiltonian graph. (English) Zbl 1393.05095

Summary: We prove the titular statement. This settles a problem of V. Chvatal [Can. Math. Bull. 16, 33–41 (1973; Zbl 0253.05142)] and encompasses earlier results of C. Thomassen [Discrete Math. 10, 383–390 (1974; Zbl 0286.05122); Lect. Notes Math. 642, 557–571 (1978; Zbl 0371.05015)], who showed it for \(K_{3}\), and J. B. Collier and E. F. Schmeichel [Discrete Math. 18, 265–271 (1977; Zbl 0367.05046)], who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI