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.[1] 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,[2] the first known counterexample to Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.[3]
The Walther graph is an identity graph; its automorphism group is the trivial group.
The characteristic polynomial of the Walther graph is :