Ungerichteter Graph/Grad/Summe/Kantenanzahl/Fakt/Beweis
Erscheinungsbild
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 .