Planar Hypohamiltonian Graphs Data

Planar Hypohamiltonian Graphs
Planar hypohamiltonian graphs are the family of planar graphs that are not Hamiltonian, but removing any of the vertecies makes them Hamiltonian. This page contains the list of smallest known planar hypohamiltonian graphs.

All of graphs of order 40, 42 and 43 are from [1] although one of the graphs on 42 were found previously in [2]. The ones of order 48, 57 and 105 are from [3], [4] and [5]; respectively.

The graph format is planar code. A complete definition can be found in the plantri manual (Appendix A). For the graphs on this page, the following should be adequate. Each graph is given as a sequence of bytes, starting with a byte containing the number of vertices. Then for each vertex, a list of the neighbours is given, one neighbour per byte in clockwise order, plus a zero byte to end the list. Vertices are numbered starting with 1. A graph with n vertices and e edges thus occupies exactly 1+2e+n bytes.

[1] M. Jooyandeh, B.D. McKay, P.R.J. Östergård, V. Pettersson, C.T. Zamfirescu, Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory, Avaliable on, PDF.
[2] G. Wiener and M. Araya, On planar hypohamiltonian graphs, J. Graph Theory, 67 (2011) 55-68.
[3] C.T. Zamfirescu and T.I. Zamfirescu, A Planar Hypohamiltonian Graph with 48 Vertices, J. Graph Theory 55(4) (2007) 338-342.
[4] W. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann., 243 (1979) 213-236 (in German).
[5] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable Graphs, Discrete Math., 14 (1976) 377-389.
40 Vertices
Graph File
Face Sequence Degree Sequence Count
05x04, 22x0530x03, 10x044684B
05x04, 22x0531x03, 08x04, 01x05101.66KB
05x04, 22x0532x03, 06x04, 02x0591.50KB
05x04, 22x0533x03, 04x04, 03x052342B
42 Vertices
Graph File
Face Sequence Degree Sequence Count
01x04, 26x0534x03, 08x045885B
01x04, 26x0535x03, 06x04, 03x052354B
07x04, 22x0530x03, 102x044724B
07x04, 22x0531x03, 10x04, 01x05284.94KB
07x04, 22x0532x03, 08x04, 02x055710.0KB
07x04, 22x0533x03, 06x04, 03x05498.66KB
07x04, 22x0533x03, 07x04, 01x05, 01x06111.94KB
07x04, 22x0534x03, 04x04, 04x05101.76KB
07x04, 22x0534x03, 05x04, 02x05, 01x065905B
07x04, 22x0534x03, 06x04, 02x0661.06KB
07x04, 22x0535x03, 04x04, 01x05, 02x062362B
43 Vertices
Graph File
Face Sequence Degree Sequence Count
04x04, 203x05, 01x736x03, 06x04, 01x061182B
04x04, 203x05, 01x737x03, 04x04, 01x05, 01x061182B
05x04, 22x05, 01x834x03, 09x0481.42KB
05x04, 22x05, 01x835x03, 07x04, 01x05203.55KB
05x04, 22x05, 01x836x03, 05x04, 02x05193.37KB
05x04, 22x05, 01x837x03, 03x04, 03x051182B
05x04, 22x05, 01x837x03, 04x04, 01x05, 01x061182B
05x04, 24x0532x03, 101x04529.34KB
05x04, 24x0533x03, 09x04, 01x0514826.5KB
05x04, 24x0534x03, 07x04, 02x0517531.4KB
05x04, 24x0534x03, 08x04, 01x062368B
05x04, 24x0535x03, 05x04, 03x055610.0KB
05x04, 24x0535x03, 06x04, 01x05, 01x0661.07KB
05x04, 24x0536x03, 03x04, 04x051184B
05x04, 24x0536x03, 04x04, 02x05, 01x064736B
05x04, 24x0537x03, 02x04, 03x05, 01x061184B
05x04, 24x0537x03, 03x04, 01x05, 02x061184B
Previously Known Ones
Graph File
Author(s) Vertex Count Face Sequence Degree Sequence
G. Wiener & M. Araya [2]421x4, 26x534x3, 8x4177B
C. T. Zamfirescu & T. Zamfirescu [3]481x4, 28x5, 1x840x3, 8x4201B
W. Hatzel [4]571x4, 28x5, 4x852x3, 5x4234B
C. Thomassen [5]10566x5, 1x1085x3, 15x4, 5x5446B
Example on 40 Vertices
JavaScript must be enabled to display this example.