Matematyka.pl

Graf nazywamy k-krytycznym, jeśli \(\displaystyle{ \chi(G)=k}\) oraz dla każdego \(\displaystyle{ v \in V(G)}\) jest \(\displaystyle{ \chi(G-v)<k}\). Wykazać, że dla każdego k-krytycznego grafu G zachodzi \(\displaystyle{ \delta(G) \ge k-1}\)

Proszę o pomoc, wskazówki.