Liczba chromatyczna a ilość krawędzi w grafie.

[studciak123]

Wykaż, że jeśli w algorytmie sekwencyjnym zostało użytych \(\displaystyle{ k}\) kolorów do pomalowania grafu, to ten graf ma przynajmniej \(\displaystyle{ \frac{ k(k-1) }{2}}\) krawędzi.

[bartek118]

Zauważ, że dla każdej pary użytych kolorów \(\displaystyle{ c_i}\), \(\displaystyle{ c_j}\) istnieje krawędź łącząca wierzchołki o tych kolorach. W związku z tym krawędzi jest przynajmniej \(\displaystyle{ \binom{k}{2} = \frac{ k(k-1) }{2}}\).