The name "Horton graph" is used for (at least) three graphs associated with Horton, illustrated above. The first is a graph on 32 vertices.
The second is a graph on 96 vertices providing a
counterexample to the Tutte bicubic graph
conjecture that every 3-regular 3-connectedbipartite graph is Hamiltonian.
The third is a smaller counterexample on 92 vertices.
(A number of even smaller counterexamples have subsequently been found.)
The 96-vertex graph is constructed using a combination of three copies of the 32-vertex graph, where the
32-vertex graph consists of two copies of the Möbius-Kantor graph with two edges
excised from each and reconnected to vertices in
the other copy (Bondy and Murty 1976, pp. 61-62).
The 32-, 92-, and 96-vertex Horton graphs have graph crossing numbers 8, 24, and 25, respectively
(E. Weisstein, Oct. 20 and 25, 2025).
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 242, 1976.Ellingham,
M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs." Dept. of
Math. Research Report No. 28. Melbourne, Australia: University of Melbourne,
1981.Ellingham, M. N. "Constructing Certain Cubic Graphs."
In Combinatorial Mathematics, IX: Proceedings of the Ninth Australian Conference
held at the University of Queensland, Brisbane, August 24-28, 1981 (Ed. E. J. Billington,
S. Oates-Williams, and A. P. Street). Berlin, Germany: Springer-Verlag,
pp. 252-274, 1982.Ellingham, M. N. and Horton, J. D.
"Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th.
Ser. B34, 350-353, 1983.Horton, J. D. "On Two-Factors
of Bipartite Regular Graphs." Disc. Math.41, 35-41, 1982.House
of Graphs. Horton Graphs. Horton
Graph 32, Horton Graph 92,
and Horton Graph 96.Owens,
P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc.
Math.44, 327-330, 1983.
