En matemáticas, la conjetura de Tait establece que "Cada grafo cúbico plano de 3 conexiones 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. Varios contraejemplos más pequeños, con 21 caras, 57 aristas y 38 vértices, fueron posteriormente demostrados como mínimos por Holton y McKay (1988) . La condición de que la gráfica sea 3-regular es necesaria debido a poliedros como el dodecaedro rómbico , que forma un grafo bipartito con vértices de seis grados cuatro en un lado y vértices de ocho grados 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 bordes de gráficas planas cúbicas sin puentes. En un gráfico plano cúbico hamiltoniano, este color 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 4 de las 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.
El contraejemplo de Tutte
Fragmento de Tutte
La clave de este contraejemplo es lo que ahora se conoce como el 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 uno de los inferiores). No puede entrar en un vértice inferior y salir por el otro.
El contraejemplo
El fragmento se puede utilizar para construir el gráfico de Tutte no hamiltoniano , juntando tres 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 tiene 3 conexiones y es plano , 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 grandes caras del dibujo, tres de las cuales están entre pares de fragmentos y la cuarta forma el exterior) truncando por multiplicación tres de sus vértices.
Contraejemplos más pequeños
Como muestran Holton y McKay (1988) , hay exactamente seis poliedros no hamiltonianos de 38 vértices que tienen cortes de tres bordes no triviales. Se forman reemplazando dos de los vértices de un prisma pentagonal por el mismo fragmento utilizado en el ejemplo de Tutte.
Ver también
- El teorema de Grinberg , una condición necesaria sobre la existencia de un ciclo hamiltoniano que se puede utilizar para demostrar que un gráfico forma un contraejemplo de la conjetura de Tait.
- La conjetura de Barnette , un refinamiento aún abierto de la conjetura de Tait que establece que cada grafo poliédrico cúbico bipartito es hamiltoniano. [1]
Notas
- ↑ Conjetura de Barnette, The Open Problem Garden, consultado el 12 de octubre de 2009.
Referencias
- Holton, DA; McKay, BD (1988), "Las gráficas planas cúbicas conectadas 3 no hamiltonianas más pequeñas tienen 38 vértices", Journal of Combinatorial Theory, Serie B , 45 (3): 305–319, doi : 10.1016 / 0095-8956 (88 ) 90075-5.
- Tait, PG (1884), "Listing's Topologie ", Philosophical Magazine , quinta serie, 17 : 30–46. Reimpreso en Scientific Papers , vol. II, págs. 85–98.
- Tutte, WT (1946), "On Hamiltonian circuits" (PDF) , Journal of the London Mathematical Society , 21 (2): 98-101, doi : 10.1112 / jlms / s1-21.2.98.
Basado en parte en una publicación de ciencia matemática de Bill Taylor , utilizada con permiso.
enlaces externos
- Weisstein, Eric W. "Conjetura del gráfico hamiltoniano de Tait" . MathWorld .