Aufgabe zu Kontengrade / Graphenalgorithmen

Question

Aufgabe:

In dieser Aufgabe betrachten wir einen beliebigen einfachen, ungerichteten Graphen \( G=(V, E) \). Ein einfacher Graph ist ein Graph ohne Schleifen und ohne parallele Kanten.

Der \( \operatorname{Grad} \operatorname{deg}(v) \) eines Knotens \( v \) in \( G \) ist die Anzahl der Kanten in \( \delta(v) \), d.h. \( \operatorname{deg}(v)=|\delta(v)| \). Beweisen Sie die folgenden Aussagen:
a) Die Summe aller Knotengrade, also \( \sum \limits_{v \in V} \operatorname{deg}(v) \), ist immer eine gerade Zahl.
b) Sofern \( G \) mindestens zwei Knoten enthält, gibt es zwei Knoten \( v \) und \( w \) mit demselben Grad, also \( \operatorname{deg}(v)=\operatorname{deg}(w) \).

Bemerkung: Aussage (a) gilt auch, wenn \( G \) nicht einfach ist. Man muss dann allerdings jede Schleife für den Knotengrad als zwei Kanten zählen.

Problem/Ansatz:

Kann mir Jemand weiterhelfen? Weiß wirklich gar nicht wie ich die Aufgabe bearbeiten soll.

Comments

a) Zähle die Anzahl der Elemente in

{ (v,e)∈VxE : v liegt auf e }

auf zwei Arten: Zähle die Anzahl zuerst über die Knoten in V, dann über die Kanten in E.

b) Angenommen nicht, dann hat ein Knoten Grad 0 und einer Grad |V|-1.

---

Möge der TS oder ein Mod. aus der Kontengerade eine Knotengerade machen.

---

Was soll denn eine Knotengerade sein?

---

Die Summe aller Knotengrade,

Grad (auch Knotengrad oder Valenz) ist ein grundlegender Begriff der Graphentheorie, eines Teilgebiets der Mathematik. Der Grad eines Knotens ist die Anzahl von Kanten, die an ihn angrenzen.

Das e war zuviel.