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.^[1] It has chromatic index 3, girth 3 and diameter 8.

Walther graph
Walther graph
Named after	Hansjoachim Walther
Vertices	25
Edges	31
Radius	5
Diameter	8
Girth	3
Automorphisms	1
Chromatic number	2
Chromatic index	3
Properties	Bipartite Planar
Table of graphs and parameters

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,^[2] the first known counterexample to Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.^[3]

Algebraic properties

The Walther graph is an identity graph; its automorphism group is the trivial group.

The characteristic polynomial of the Walther graph is :

${\displaystyle {\begin{aligned}x^{3}\left(x^{22}\right.&{}-31x^{20}+411x^{18}-3069x^{16}+14305x^{14}-43594x^{12}\\&\left.{}+88418x^{10}-119039x^{8}+103929x^{6}-55829x^{4}+16539x^{2}-2040\right)\end{aligned}}}$