\alpha(G)>=abs(V(G))/(\Delta+1)

abs(N)=abs(V(G))-\alpha<=\alpha*\Delta

Wir zeigen zwei Aussagen:

  i) N+\alpha=V
  ii)N  <=  \alpha \Delta

Zu i) 
Betrachte eine maximal unabhängige Menge A in dem Graphen und bezeichne N  die Menge und auch die Anzahl seiner Nachbarn. Falls nun
eine Ecke a \in V\\A in N nicht vorkommen würde, so könnten wir A mit dieser Ecke a erweitern ->darf nicht sein, da ja A schon maximal ist. Also definieren A und N eine Partition von V.

Zu ii) 
Von jeder Ecke in A gehen höchstens \Delta Kanten aus. 

Aus i)  und ii) folgt dann die gewünschte Ungleichung

Viele Grüße,
CC