grafy-zachłanny algorytm kolorowania

[borubarek]

zad.1
Uporządkujmy wierzchołki grafu \(\displaystyle{ G}\) w taki sposób, że \(\displaystyle{ d(x_1)\geq d(x_2)\geq \ldots \geq d(x_n)}\). Pokazać, że przy takim uporządkowaniu wierzchołków, zachłanny algorytm kolorowania wykorzysta najwyżej \(\displaystyle{ \max_{i}\min\{d(x_i)+1,i\}}\) kolorów. Wywnioskować z tego, że jeśli \(\displaystyle{ k}\) jest największą liczbą taką, że \(\displaystyle{ k\leq d(x_k)+1}\), to \(\displaystyle{ \chi (G)\leq k}\).
zad.2
Z poprzedniego zadania wywnioskować, że \(\displaystyle{ \chi (G)+\chi (\overline{G})\leq n+1}\).

[UNIX_admin]

1. czego nie rozumiesz?
2. do czego jest Ci potrzebnie rozwiazanie tych zadan?

[borubarek]

Sprawdziłem to na przykładach, ale nie wiem, jak to rozpisać na przypadku ogólnym. Zadania są mi potrzebne do zaliczenia ćwiczeń z matematyki dyskretnej