## 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.

### MSC:

 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.)

### Keywords:

hypo-Hamiltonian graph; induced subgraph

### Citations:

Zbl 0253.05142; Zbl 0286.05122; Zbl 0371.05015; Zbl 0367.05046
Full Text: