Other larger non-Hamiltonian cubic polyhedral graphs include the 46-vertex Tutte graph and a 44-vertex graph found by Emanuels Grīnbergs using Grinberg's theorem.
The Barnette–Bosák–Lederberg graph has a similar construction to the Tutte graph but is composed of two Tutte fragments, connected through a pentagonal prism, instead of three connected through a tetrahedron.
Without the constraint of having exactly three edges at every vertex, much smaller non-Hamiltonian polyhedral graphs are possible, including the Goldner–Harary graph and the Herschel graph.
References
^Holton, D. A.; McKay, B. D. (1988), "The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices", Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5
^Bosák, J. (1967), "Hamiltonian lines in cubic graphs", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 35–46, MR0221970