Teoria grafów

[Antia]

Uzasadnij, że indeks chromatyczny grafu Petersena wynosi \(\displaystyle{ 4}\) i wywnioskuj stąd, że graf ten nie jest hamiltonowski.


Mam zrobioną część pierwszą, że jego indeks chromatyczny jest \(\displaystyle{ 4}\) ale nie widzę na tej podstawie dlaczego nie jest hamiltonowski.

[Zordon]

Gdyby był hamiltonowski to 3 kolory wystarczyłyby. Wyobraź sobie cykl hamiltona, jego krawędzie kolorujemy na zmianę na kolory 1, 2. Resztę krawędzi: cięciwy kolorujemy na 3 kolor.