[Kombinatoryka] Kolorowa klika

[kaszubki]

Dana jest klika \(\displaystyle{ n-\text{elementowa}}\). Wierzchołki i krawędzie kolorujemy w taki sposób, że
1) żadne dwie krawędzie o wspólnym końcu nie są tego samego koloru
2) wierzchołek i krawędzie z niego wychodzące są różnych kolorów

Wyznacz minimalną liczbę kolorów, którymi można pokolorować ten graf, aby spełnione były te 2 założenia.

[marcin_smu]

Ukryta treść:    

Krawędzie każdego grafu da się pokolorować k+1 kolorami gdzie k to największy stopień wierzchołka. Skąd w prosty sposób wynika, iż do pokolorowania kliki zgodnie z założeniami wystarczy n kolorów.