En el campo matemático de la teoría de grafos , el gráfico de Tutte es un gráfico de 3 regulares con 46 vértices y 69 aristas que lleva el nombre de WT Tutte . [1] Tiene número cromático 3, índice cromático 3, circunferencia 4 y diámetro 8.
El gráfico de Tutte es un gráfico poliédrico cúbico , pero no hamiltoniano . Por lo tanto, es un contraejemplo a la conjetura de Tait que cada poliedro de 3 regulares tiene un ciclo hamiltoniano. [2]
Publicado por Tutte en 1946, es el primer contraejemplo construido para esta conjetura. [3] Posteriormente se encontraron otros contraejemplos, en muchos casos basados en el teorema de Grinberg .
A partir de un pequeño gráfico plano llamado fragmento de Tutte, WT Tutte construyó un poliedro no hamiltoniano, juntando tres de esos fragmentos. 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 resultante es triconexa y plana , por lo que según el teorema de Steinitz es la gráfica de un poliedro. Tiene 25 caras.
Se puede realizar geométricamente a partir de un tetraedro (cuyas caras corresponden a las cuatro grandes caras de nueve lados 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. .
El grupo de automorfismos del gráfico de Tutte es Z /3 Z , el grupo cíclico de orden 3.
El polinomio característico del gráfico de Tutte es:
Aunque el gráfico de Tutte es el primer gráfico poliédrico no hamiltoniano de 3 regulares que se descubre, no es el gráfico más pequeño.
En 1965, Lederberg encontró el gráfico de Barnette-Bosák-Lederberg en 38 vértices. [4] [5] En 1968, Grinberg construyó pequeños contraejemplos adicionales a la conjetura de Tait: los gráficos de Grinberg en 42, 44 y 46 vértices. [6] En 1974, Faulkner y Younger publicaron dos gráficos más: los gráficos de Faulkner-Younger en 42 y 44 vértices. [7]
Finalmente, Holton y McKay demostraron que 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. [8]
