Dowód na nie istnienie danego grafu

[tomek1172]

Wykaż, że nie istnieje graf na 10 wierzchołkach o obwodzie 4 i liczbie chromatycznej 4. Z czego tutaj najlepiej skorzystać?

[Mruczek]

Założenie o obwodzie 4 można osłabić do braku trójkątów w tym grafie.
Wtedy może to pomoże:

Kod: Zaznacz cały

https://math.stackexchange.com/questions/792091/why-must-a-triangle-free-4-chromatic-graph-have-at-least-11-vertices