En el campo matemático de la teoría de grafos , el grafo de Tutte es un grafo 3-regular 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 grafo de Tutte es un grafo poliédrico cúbico , pero no es hamiltoniano . Por lo tanto, es un contraejemplo de la conjetura de Tait de que todo poliedro 3-regular tiene un ciclo hamiltoniano. [2]
Publicado por Tutte en 1946, es el primer contraejemplo construido para esta conjetura. [3] Otros contraejemplos se encontraron posteriormente, en muchos casos basados en el teorema de Grinberg .
A partir de un pequeño grafo plano llamado fragmento de Tutte, WT Tutte construyó un poliedro no hamiltoniano, juntando tres de esos fragmentos. Las aristas "obligatorias" de los fragmentos, que deben ser parte de cualquier camino hamiltoniano a través del fragmento, están conectadas en el vértice central; como cualquier ciclo puede utilizar solo dos de esas tres aristas, no puede haber ciclo hamiltoniano.
El grafo resultante es 3-conexo y plano , por lo que, según el teorema de Steinitz, es el grafo 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 grafo de Tutte es Z /3 Z , el grupo cíclico de orden 3.
El polinomio característico del grafo de Tutte es:
Aunque el gráfico de Tutte es el primer gráfico poliédrico no hamiltoniano de 3 regularidades que se descubrió, no es el gráfico más pequeño de su tipo.
En 1965, Lederberg encontró el grafo 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 grafos de Grinberg en 42, 44 y 46 vértices. [6] En 1974, Faulkner y Younger publicaron dos grafos más: los grafos 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 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. [8]
