Walther Graphs

There are at least two graphs associated with H. Walther.


The graph on 25 vertices illustrated above which is a variant of Tutte's fragment is depicted in Problem 2.10 of Harary (1994, p. 24; cf. Pemmaraju and Skiena(2003, p. 23). This graph is implemented in the Wolfram Language as GraphData["WaltherGraph25"].


A cubic nonhamiltonian graph on 162 vertices due Walther (1965) appears in Grünbaum (2003, Fig. 17.1.9, p. 366). It provides a counterexample to a conjecture of Hunter (1962) that all cyclically 5-connected polyhedral graphs contain a Hamiltonian cycle (Grünbaum 2003, p. 365). This graph will is implemented in the Wolfram Language as GraphData["WaltherGraph162"].

See also

Cubic Nonhamiltonian Graph, Tutte's Fragment

Explore with Wolfram|Alpha


Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Hunter, H. F. On Non-Hamiltonian Maps and their Duals. Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.

Cite this as:

Weisstein, Eric W. "Walther Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications