In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton.

[1] Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.

[2][3] After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found.

Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices).

[4][5] The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78.

[6] At that time, it was the smallest known counterexample to the Tutte conjecture.

The second one was published by Ellingham and Horton in 1983 and was of order 54.

[7] In 1989, Georges' graph, the smallest currently-known non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.

[8] As a non-Hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.

[9] The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10, girth 6, book thickness 3[10] and queue number 2.

[10] It is also a 3-edge-connected graph.

The automorphism group of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×S4, the direct product of the Klein four-group and the symmetric group S4.

The characteristic polynomial of the Horton graph is :

( x − 3 ) ( x − 1

)