Walther graph

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

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.

Algebraic properties

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

The characteristic polynomial of the Walther graph is :

${\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}}$