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.

Walther graph
Walther graph
Named afterHansjoachim Walther
Vertices25
Edges31
Radius5
Diameter8
Girth3
Automorphisms1
Chromatic number2
Chromatic index3
PropertiesBipartite
Planar
Table of graphs and parameters

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]

Algebraic properties

edit

The Walther graph is an identity graph; its automorphism group is the trivial group.

The characteristic polynomial of the Walther graph is :

 

References

edit
  1. ^ Weisstein, Eric W. "Walther Graph". MathWorld.
  2. ^ 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
  3. ^ Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.