 Tait conjectured that every cubic polyhedral graph (that is, a polyhedral graph in which each vertex is incident to exactly three edges) has a Hamiltonian cycle, but this conjecture was disproved by a counterexample of W. T. Tutte, the polyhedral but non-Hamiltonian Tutte graph.If one relaxes the requirement that the graph be cubic, there are much smaller non-Hamiltonian polyhedral graphs.The graph with the fewest vertices and edges is the 11-vertex and 18-edge Herschel graph, and there also exists an 11-vertex non-Hamiltonian polyhedral graph in which all faces are triangles, the Goldner–Harary graph.