En el campo matemático de la teoría de grafos , los gráficos de Ellingham-Horton son dos gráficos regulares de 3 en 54 y 78 vértices: el gráfico de 54 de Ellingham-Horton y el gráfico de 78 de Ellingham-Horton . [1] Llevan el nombre de Joseph D. Horton y Mark N. Ellingham , sus descubridores. Estos dos gráficos proporcionan contraejemplos a la conjetura de WT Tutte de que todo gráfico bipartito cúbico conectado en 3 es hamiltoniano . [2] El grosor del libro del gráfico de 54 de Ellingham-Hortony el gráfico 78 de Ellingham-Horton es 3 y los números de cola 2. [3]
El primer contraejemplo a la conjetura de Tutte fue el gráfico de Horton , publicado por Bondy & Murty (1976) . [4] Después del gráfico de Horton, se encontraron varios contraejemplos más pequeños a la conjetura de Tutte. Entre ellos se encuentran un gráfico de 92 vértices de Horton (1982) , [5] un gráfico de 78 vértices de Owens (1983) , [6] y los dos gráficos de Ellingham-Horton.
El primer gráfico de Ellingham-Horton fue publicado por Ellingham (1981) y es de orden 78. [7] En ese momento era el contraejemplo más pequeño conocido de la conjetura de Tutte. El segundo gráfico de Ellingham-Horton fue publicado por Ellingham & Horton (1983) y es de orden 54. [8] En 1989, se descubrió el gráfico de Georges, el gráfico bipartito cúbico no hamiltoniano 3 conectado más pequeño conocido actualmente, que contiene 50 vértices. [9]