Liczba chromatyczna dowód

mCichy13 · Post autor: **mCichy13** » 5 sty 2015, o 03:42

Udowodnij

\(\displaystyle{ \chi(G)\left( \chi (G)-1\right) \le 2\left| E\right|}\)

Od czego powinienem zacząć żeby taki coś pokazać?

bakala12 · Post autor: **bakala12** » 5 sty 2015, o 11:37

Zacznij od pokazania lematu. W każdym grafie pokolorowanym na \(\displaystyle{ \chi(G)}\) kolorów istnieje przynajmniej jeden wierzchołek w każdym kolorze stopnia co najmniej \(\displaystyle{ \chi(G)-1}\).
Teza wynika z tego lematu i lematu o uściskach dłoni.