Walther graph
From Wikipedia, the free encyclopedia
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.
Quick Facts Named after, Vertices ...
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 |
Close
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]