Walther graph
| Walther graph | |
|---|---|
| File:240px 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]
By integrating these subgraphs into a complex 46-vertex structure, Tutte demonstrated that certain 3-regular planar graphs lack the symmetry required for a Hamiltonian cycle. This construction effectively bridged the gap between local vertex connectivity and the global properties of polyhedral graphs.
Algebraic properties
The Walther graph is an identity graph; its automorphism group is the trivial group.
The characteristic polynomial of the Walther graph is :
References
- ↑ Weisstein, Eric W.. "Walther Graph". http://mathworld.wolfram.com/WaltherGraph.html.
- ↑ Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98, http://jlms.oxfordjournals.org/cgi/reprint/s1-21/2/98.pdf
- ↑ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
 |  |
