La conjetura de Barnette es un problema no resuelto de la teoría de grafos , una rama de las matemáticas , que se refiere a los ciclos hamiltonianos en grafos. Recibe su nombre en honor a David W. Barnette, profesor emérito de la Universidad de California, Davis ; afirma que todo grafo poliédrico bipartito con tres aristas por vértice tiene un ciclo hamiltoniano.
Un grafo plano es un grafo no dirigido que puede ser embebido en el plano euclidiano sin ningún cruce . Un grafo plano se llama poliédrico si y solo si es 3-vértices-conexos , es decir, si no existen dos vértices cuya eliminación desconectaría el resto del grafo. Un grafo es bipartito si sus vértices pueden ser coloreados con dos colores diferentes de tal manera que cada arista tenga un punto final de cada color. Un grafo es cúbico (o 3-regular ) si cada vértice es el punto final de exactamente tres aristas. Finalmente, un grafo es hamiltoniano si existe un ciclo que pasa por cada uno de sus vértices exactamente una vez. La conjetura de Barnette establece que todo grafo poliédrico bipartito cúbico es hamiltoniano.
Según el teorema de Steinitz , un grafo plano representa las aristas y vértices de un poliedro convexo si y solo si es poliédrico. Un poliedro tridimensional tiene un grafo cúbico si y solo si es un poliedro simple . Y, un grafo plano es bipartito si y solo si, en una incrustación plana del grafo, todos los ciclos de las caras tienen una longitud par. Por lo tanto, la conjetura de Barnette puede enunciarse en una forma equivalente: supongamos que un poliedro convexo simple tridimensional tiene un número par de aristas en cada una de sus caras. Entonces, según la conjetura, el grafo del poliedro tiene un ciclo hamiltoniano.
PG Tait (1884) conjeturó que todo grafo poliédrico cúbico es hamiltoniano; esto llegó a conocerse como la conjetura de Tait . Fue refutada por WT Tutte (1946), quien construyó un contraejemplo con 46 vértices; otros investigadores encontraron más tarde contraejemplos aún más pequeños. Sin embargo, ninguno de estos contraejemplos conocidos es bipartito. El propio Tutte conjeturó que todo grafo bipartito cúbico 3-conexo es hamiltoniano, pero se demostró que esto era falso mediante el descubrimiento de un contraejemplo, el grafo de Horton . [1] David W. Barnette (1969) propuso una combinación debilitada de las conjeturas de Tait y Tutte, afirmando que todo poliedro cúbico bipartito es hamiltoniano o, equivalentemente, que todo contraejemplo de la conjetura de Tait es no bipartito.
Kelmans (1994) [2] demostró que la conjetura de Barnette es equivalente a una afirmación superficialmente más fuerte: que por cada dos aristas e y f en la misma cara de un poliedro cúbico bipartito, existe un ciclo hamiltoniano que contiene a e pero no contiene a f . Claramente, si esta afirmación es verdadera, entonces cada poliedro cúbico bipartito contiene un ciclo hamiltoniano: basta con elegir e y f arbitrariamente. En otras direcciones, Kelmans demostró que un contraejemplo podría transformarse en un contraejemplo de la conjetura original de Barnette.
La conjetura de Barnette es también equivalente a la afirmación de que los vértices del dual de cada grafo poliédrico cúbico bipartito pueden ser divididos en dos subconjuntos cuyos subgrafos inducidos son árboles. El corte inducido por dicha división en el grafo dual corresponde a un ciclo hamiltoniano en el grafo primal. [3]
Aunque la verdad de la conjetura de Barnette sigue siendo desconocida, los experimentos computacionales han demostrado que no existe ningún contraejemplo con menos de 86 vértices. [4]
Si la conjetura de Barnette resulta ser falsa, entonces se puede demostrar que es NP-completo para probar si un poliedro cúbico bipartito es hamiltoniano. [5] Si un grafo planar es bipartito y cúbico pero solo de conectividad 2, entonces puede ser no hamiltoniano, y es NP-completo para probar la hamiltonicidad de estos grafos. [6] Alt et al. (2016) obtuvieron otro resultado: si el grafo dual puede ser coloreado en vértices con los colores azul, rojo y verde de modo que cada ciclo rojo-verde contenga un vértice de grado 4, entonces el grafo primal es hamiltoniano.
Una conjetura relacionada de Barnette afirma que todo grafo poliédrico cúbico en el que todas las caras tienen seis o menos aristas es hamiltoniano. Los experimentos computacionales han demostrado que, si existe un contraejemplo, debería tener más de 177 vértices. [7] La conjetura fue demostrada por Kardoš (2020).
La intersección de estas dos conjeturas sería que todo grafo poliédrico cúbico bipartito en el que todas las caras tienen cuatro o seis aristas es hamiltoniano. Goodey (1975) demostró que esto es cierto.