Ungerichteter Graph/Grad/Summe/Kantenanzahl/Fakt/Beweis

Beweis

Das kann man beispielsweise durch Induktion über die Anzahl der Kanten bei gegebener Knotenmenge beweisen. Beim einem kantenlosen Graphen steht links und rechts beidseitig . Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte und verbindet, so erhöht sich der Grad von und der Grad von jeweils um und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um .