Kolorowanie grafów - liczba chromatyczna

[flashion]

Mam do rozwiązania takie zadanie o kolorowaniu grafów:
Teoria:
Liczba chromatyczna grafu \(\displaystyle{ G}\), oznaczana przez \(\displaystyle{ \chi (G)}\), to najmniejsza liczba \(\displaystyle{ k}\) taka, ze
istnieje poprawne kolorowanie wierzchołków grafu \(\displaystyle{ G}\) uzywajace \(\displaystyle{ k}\) kolorów.
Zadanie:
Wykaż, że każdy graf ma podgraf o minimalnym stopniu co najmniej \(\displaystyle{ \chi (G)+1}\).