Herschel graph
Hamiltonicity

As a bipartite graph that has an odd number of vertices, the Herschel graph does not contain a Hamiltonian cycle (a cycle of edges that passes through each vertex exactly once). For, in any bipartite graph, any cycle must alternate between the vertices on either side of the bipartition, and therefore must contain equal numbers of both types of vertex and must have an even length. Thus, a cycle passing once through each of the eleven vertices cannot exist in the Herschel graph. A graph is called Hamiltonian whenever it contains a Hamiltonian cycle, so the Herschel graph is not Hamiltonian. It has the smallest number of vertices, the smallest number of edges, and the smallest number of faces of any non-Hamiltonian polyhedral graph. There exist other polyhedral graphs with 11 vertices and no Hamiltonian cycles (notably the Goldner–Harary graph) but none with fewer edges.

All but three of the vertices of the Herschel graph have degree three. A graph is called cubic or 3-regular when all of its vertices have degree three. P. G. Tait conjectured that a polyhedral 3-regular graph must be Hamiltonian; this was disproved when W. T. Tutte provided a counterexample, the Tutte graph, which is much larger than the Herschel graph. A refinement of Tait's conjecture, Barnette's conjecture that every bipartite 3-regular polyhedral graph is Hamiltonian, remains open.

Every maximal planar graph that does not have a Hamiltonian cycle has a Herschel graph as a minor. The Herschel graph is conjectured to be one of three minor-minimal non-Hamiltonian 3-vertex-connected graphs. The other two are the complete bipartite graph K 3, 4 {\displaystyle K_{3,4}} and a graph formed by splitting both the Herschel graph and K 3, 4 {\displaystyle K_{3,4}} into two symmetric halves by three-vertex separators and then combining one half from each graph.

The Herschel graph also provides an example of a polyhedral graph for which the medial graph has no Hamiltonian decomposition into two edge-disjoint Hamiltonian cycles. The medial graph of the Herschel graph is a 4- regular graph with 18 vertices, one for each edge of the Herschel graph; two vertices are adjacent in the medial graph whenever the corresponding edges of the Herschel graph are consecutive on one of its faces. It is 4-vertex-connected and essentially 6-edge-connected. Here, a graph is k {\displaystyle k} -vertex-connected or k {\displaystyle k} -edge-connected if the removal of fewer than k {\displaystyle k} vertices or edges (respectively) cannot disconnected it. Planar graphs cannot be 6-edge-connected, because they always have a vertex of degree at most five, and removing the neighboring edges disconnects the graph. The "essentially 6-edge-connected" terminology means that this trivial way of disconnecting the graph is ignored, and it is impossible to disconnect the graph into two subgraphs that each have at least two vertices by removing five or fewer edges.
language:response_language[Dutch], startend:quotation