Ellingham-Horton graph
Encyclopedia
In the mathematical
field of graph theory
, the Ellingham–Horton graphs are two 3-regular graph
s on 54 and 78 vertices : the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte
that every cubic
3-connected bipartite graph
is Hamiltonian.
The first counterexample to the Tutte conjecture was the Horton graph
, published by . After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by , a 78-vertex graph by , and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by and is of order 78. At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by and is of order 54. In 1989, George's graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Ellingham–Horton graphs are two 3-regular graph
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
s on 54 and 78 vertices : the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
that every cubic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
3-connected bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
is Hamiltonian.
The first counterexample to the Tutte conjecture was the Horton graph
Horton graph
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...
, published by . After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by , a 78-vertex graph by , and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by and is of order 78. At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by and is of order 54. In 1989, George's graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.