| Tutte graph | |
|---|---|
 Tutte graph | |
| Named after | W. T. Tutte |
| Vertices | 46 |
| Edges | 69 |
| Radius | 5 |
| Diameter | 8 |
| Girth | 4 |
| Automorphisms | 3 (Z/3Z) |
| Chromatic number | 3 |
| Chromatic index | 3 |
| Properties | Cubic Planar Polyhedral |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte.[1] It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.
The Tutte graph is a cubic polyhedral graph, but is non-hamiltonian. Therefore, it is a counterexample to Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.[2]
Published by Tutte in 1946, it is the first counterexample constructed for this conjecture.[3] Other counterexamples were found later, in many cases based on Grinberg's theorem.
- ^ Weisstein, Eric W. "Tutte's Graph". MathWorld.
- ^ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
- ^ Tutte, W. T. (1946), "On Hamiltonian circuits" (PDF), Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98.