¿Hay un gráfico sin un$K_5$ menor que tenga un número cromático de$5$?

Question

Ahora, yo no puedo pensar en ninguna forma de una gráfica para exigir $5$ colores todavía no tienen un $K_5$ menor ($5$ vértices conectados el uno al otro). Si en verdad no hay tal gráfica, entonces cada gráfico que requiere de $5$ colores debe tener un $K_5$ menor de edad, que por el teorema de Kuratowski significa que estos gráficos no son planas. Por lo tanto, cada plano gráfico es de al menos 4 engañosa.

Dudo mucho que la prueba del teorema de los cuatro colores es así de simple, así que es posible que alguien me muestre un contraejemplo a mi argumento?

Answer 1

Ver el artículo de Wikipedia sobre el Hadwiger conjetura. La conjetura de los estados (como un caso especial) que un $5$-engañosa gráfico debe contener una $K_5$ menor. Este hecho nunca ha sido probado directamente, sin embargo ha demostrado ser equivalente a la de cuatro colores teorema. Desde los cuatro-color teorema es verdadero, sabemos que el Hadwiger conjetura es verdadera para cinco colores, y por lo que ningún gráfico del tipo que usted describe que existe.