En matemáticas, la conjetura de Tait establece que "Todo gráfico cúbico plano de 3 conexos tiene un ciclo hamiltoniano (a lo largo de las aristas) 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 grafo sea 3-regular es necesaria debido a poliedros como el dodecaedro rómbico , que forma un grafo bipartito con seis vértices de grado cuatro en un lado y ocho vértices de grado tres en el otro lado; Debido a que cualquier ciclo hamiltoniano tendría que alternar entre los dos lados de la bipartición, pero tienen un número desigual 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 lo describió Tait, el problema de los cuatro colores es equivalente al problema de encontrar coloraciones de tres aristas en gráficos planos cúbicos sin puentes . En un gráfico plano cúbico hamiltoniano, esta coloración de aristas es fácil de encontrar: utilice dos colores alternativamente en el ciclo y un tercer color para todas las aristas restantes. Alternativamente, se puede construir directamente una coloración de 4 caras de un gráfico plano cúbico hamiltoniano, utilizando dos colores para las caras dentro del ciclo y dos colores más para las caras exteriores.
La clave de este contraejemplo es lo que ahora se conoce como fragmento de Tutte , que se muestra a la derecha.
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 de cualquiera de los inferiores). No puede entrar por un vértice inferior y salir por el otro.
Luego, el fragmento se puede utilizar para construir el gráfico Tutte no hamiltoniano , juntando tres de esos fragmentos como se muestra en la imagen. Los bordes "obligatorios" de los fragmentos, que deben formar parte de cualquier camino hamiltoniano a través del fragmento, están conectados en el vértice central; debido a que cualquier ciclo puede utilizar sólo dos de estas tres aristas, no puede haber un ciclo hamiltoniano.
La gráfica de Tutte resultante es triconexa y plana , por lo que según el teorema de Steinitz es la gráfica 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 grandes del dibujo, tres de las cuales están entre pares de fragmentos y la cuarta forma el exterior) truncando multiplicadamente tres de sus vértices.
Como muestran Holton y McKay (1988), hay exactamente seis poliedros no hamiltonianos de 38 vértices que tienen cortes no triviales de tres aristas. Se forman sustituyendo dos de los vértices de un prisma pentagonal por el mismo fragmento utilizado en el ejemplo de Tutte.
Basado en parte en una publicación de ciencia matemática de Bill Taylor, utilizada con permiso.