La conjetura de Tate es una conjetura matemática refutada de que cualquier gráfico cúbico plano conectado en 3 tiene un ciclo hamiltoniano que pasa por todos sus vértices .
Enunciado en 1884 por Peter Tate [1] , refutado en 1946 por William Tutt [2] , quien construyó un contraejemplo con 25 caras, 69 aristas y 46 vértices, el grafo Tatta . Posteriormente, en 1988, se encontró un contraejemplo con 21 caras, 57 aristas y 38 vértices y se demostró que este grafo es mínimo [3] .
La condición de 3-regularidad (los gráficos 3-regulares se llaman cúbicos) es necesaria porque hay poliedros como el dodecaedro rómbico . El dodecaedro rómbico forma un gráfico bipartito , y cualquier ciclo hamiltoniano en este gráfico debe cambiar alternativamente las partes (lados) del gráfico, por lo que el número de vértices en las partes debe ser igual, pero el gráfico tiene seis vértices de grado 4 en uno lado y ocho vértices de grado 3 en el otro.
Si la conjetura fuera cierta, entonces se seguiría una solución simple al problema de los cuatro colores . Según Tate, el problema de los cuatro colores es equivalente al problema de encontrar una coloración de 3 líneas 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: usamos alternativamente dos colores para colorear los bordes a lo largo del ciclo hamiltoniano y coloreamos los bordes restantes con el tercer color. Alternativamente, se puede construir una coloración de cuatro colores de las caras de un gráfico planar cúbico hamiltoniano directamente usando dos colores para colorear las caras dentro del ciclo y dos colores para las caras fuera.
La clave del contraejemplo es el gráfico, ahora llamado fragmento Tutta . Si este fragmento es parte de un gráfico más grande, cualquier ciclo hamiltoniano debe pasar por el borde (colgante) en el vértice superior (y por uno de los bordes inferiores). Un camino no puede entrar por un borde inferior y salir por otro borde inferior.
El fragmento de Tutt se utiliza para construir un gráfico de Tutt no hamiltoniano , si se suman tres de esos fragmentos. Los bordes "obligatorios" de los fragmentos, que deben ser parte del camino hamiltoniano a través del fragmento, están conectados en el centro. Dado que cualquier ciclo solo puede pasar por dos de los tres bordes en el centro, no puede haber un ciclo hamiltoniano para este gráfico. El grafo de Tutt resultante es 3-conexo y plano , por lo que es un grafo politópico según el teorema de Steinitz . El gráfico tiene 25 caras, 69 aristas y 46 vértices. Geométricamente, se puede obtener un gráfico a partir de un tetraedro (cuyas caras corresponden a las cuatro caras grandes de la figura: tres caras entre pares de fragmentos, y la cuarta cara es la exterior) truncando repetidamente tres de sus vértices.
Como demostraron Holton y McKay en 1988 [3] , hay exactamente seis poliedros no hamiltonianos de 3 regulares con 38 vértices. Los poliedros se forman reemplazando dos vértices de un prisma pentagonal con el mismo fragmento del ejemplo de Tutta.