There are (at least) three graphs associated with Horton, illustrated above. The first is a graph on 32 nodes. The second is a graph on 96 nodes providing a counterexample
to the Tutte conjecture that every 3-regular
3-connected bipartite graph is Hamiltonian (left
figure above). The third is a smaller counterexample on 92 nodes (right figure above).
(A number of even smaller counterexamples have subsequently been found.)
The 96-node graph is constructed using a clever combination of three copies of the 32-node graph, where the 32-node graph consists of two copies of the Möbius-Kantor
graph with two edges excised from each and reconnected to vertives in the other
copy (Bondy and Murty 1976, pp. 61-62).
The 32-, 92- and 96-Horeon 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." Research
Report No. 28, Dept. of Math., Univ. Melbourne, 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: 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.Owens, P. J. "Bipartite Cubic Graphs and a Shortness
Exponent." Disc. Math.44, 327-330, 1983.
