Análisis combinatorio: problema demuestre que el número cromático de K5 es 5...
- Demuestre que el número cromático de k_{5} es 5, ¿Contradice este resultado el teorema de los 4 colores?, ¿Por qué?.
2 respuestas
·
·
¡Hola Carolinaboni!
El grafo k_{5} es el compuesto por 5 vértice y todas las aristas posibles entre sus elementos.
Si el número cromático fuera menor de 5 entonces habría al menos un par de vértices con el mismo color, y como hay una arista que los une entraríamos en contradicción con que su número cromático es menor de 5.
No, no contradice el teorema de los 4 colores porque los grafos planos de los mapas no se corresponden con grafos de vértices completos. Si alguno de 5 regiones o más fuese completo sí que habría contradicción.
Mándame la teoría que no tengo ni idea de esto.
Y eso es todo, saludos.
:
:
Supongamos que no, entonces podemos pintar el grafo con 4 colores (o menos), pero si tenemos 5 vértices coloreados con 4 colores, entonces debe haber por lo menos 2 vértices con el mismo color y esto es absurdo porque K_5 es completo.
No contradice al teorema de 4 colores porque una de las premisas del teorema es que el grafo debe ser planar, pero K_5 no lo es (de hecho es el completo de menor cantidad de vértices que es no planar).