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 ${}0$. Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte ${}u$ und ${}v$ verbindet, so erhöht sich der Grad von ${}u$ und der Grad von ${}v$ jeweils um ${}1$ und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um ${}2$.

Zur bewiesenen Aussage