Walther graph

In the mathematical field of graph theory, the Walther graph, also called the Tutte fragment, is a planar bipartite graph with 25 vertices and 31 edges named after Hansjoachim Walther. It has chromatic index 3, girth 3 and diameter 8.
If the single vertex of degree 1 whose neighbour has degree 3 is removed, the resulting graph has no Hamiltonian path. This property was used by Tutte when combining three Walther graphs to produce the Tutte graph, the first known counterexample to Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.
By integrating these subgraphs into a complex 46-vertex structure, Tutte demonstrated that certain 3-regular planar graphs lack the symmetry required for a Hamiltonian cycle. This construction effectively bridged the gap between local vertex connectivity and the global properties of polyhedral graphs.

Algebraic properties

The Walther graph is an identity graph; its automorphism group is the trivial group.
The characteristic polynomial of the Walther graph is :