Walther graph

Template:Short description Template:Infobox 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.

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{array}{cc}{x}^3(x^{22}& -31x^{20}+411x^{18}-3069x^{16}+14305x^{14}-43594x^{12}\\ & +88418x^{10}-119039x^8+103929x^6-55829x^4+16539x^2-2040)\end{array}$

References

Template:Graph-stub