En matemáticas, la conjetura de Tait establece que "Todo gráfico cúbico plano conectado en 3 tiene un ciclo hamiltoniano (a lo largo de los bordes) a través de todos sus vértices ". Fue propuesto por PG Tait ( 1884 ) y refutado por WT Tutte ( 1946 ), quien construyó un contraejemplo con 25 caras, 69 aristas y 46 vértices. Holton y McKay (1988) demostraron posteriormente que varios contraejemplos más pequeños, con 21 caras, 57 aristas y 38 vértices, eran mínimos . La condición de que el gráfico sea 3-regular es necesaria debido a poliedros como el dodecaedro rómbico , que forma un gráfico bipartito con seis vértices de grado cuatro en un lado y ocho vértices de grado tres en el otro lado; porque cualquier ciclo hamiltoniano tendría que alternar entre los dos lados de la bipartición, pero tienen números desiguales de vértices, el dodecaedro rómbico no es hamiltoniano.
La conjetura era significativa porque, de ser cierta, habría implicado el teorema de los cuatro colores : como describió Tait, el problema de los cuatro colores es equivalente al problema de encontrar coloraciones de 3 aristas de gráficos planos cúbicos sin puente . En un gráfico planar cúbico hamiltoniano, tal coloración de borde es fácil de encontrar: use dos colores alternativamente en el ciclo y un tercer color para todos los bordes restantes. Alternativamente, se puede construir directamente una coloración en 4 de las caras de un gráfico planar cúbico hamiltoniano, usando dos colores para las caras dentro del ciclo y dos colores más para las caras fuera.
Si este fragmento es parte de un gráfico más grande, entonces cualquier ciclo hamiltoniano a través del gráfico debe entrar o salir del vértice superior (y cualquiera de los inferiores). No puede entrar por un vértice inferior y salir por el otro.
Luego, el fragmento se puede usar para construir el gráfico de Tutte no hamiltoniano , juntando tres de esos fragmentos como se muestra en la imagen. Los bordes "obligatorios" de los fragmentos, que deben ser parte de cualquier camino hamiltoniano a través del fragmento, están conectados en el vértice central; debido a que cualquier ciclo puede usar solo dos de estos tres bordes, no puede haber un ciclo hamiltoniano.
El gráfico de Tutte resultante es plano y conexo en 3 , por lo que, según el teorema de Steinitz , es el gráfico de un poliedro. En total tiene 25 caras, 69 aristas y 46 vértices. Se puede realizar geométricamente a partir de un tetraedro (cuyas caras corresponden a las cuatro caras grandes del dibujo, tres de las cuales están entre pares de fragmentos y la cuarta forma el exterior) truncando de forma múltiple tres de sus vértices.
Como muestran Holton y McKay (1988) , hay exactamente seis poliedros no hamiltonianos de 38 vértices que tienen cortes de tres aristas no triviales. Se forman reemplazando dos de los vértices de un prisma pentagonal por el mismo fragmento utilizado en el ejemplo de Tutte.