Graphen, Knoten, Grad beweisen

Question

Aufgabe:

Sei \( G=(V, E) \) ein (einfacher, endlicher, ungerichteter) Graph. Beweisen Sie die folgende Aussage:
Gilt \( |V| \geq 2, \) so existieren zwei Knoten \( v_{1}, v_{2} \in V, v_{1} \neq v_{2} \) mit gleichem Grad \( d e g\left(v_{1}\right)=d e g\left(v_{2}\right) \)

Problem/Ansatz:

Für Ansätze sowie Lösungen zur Kontrolle wäre ich sehr dankbar :)

Answer 1

Hallo,

betrachte die Abbildung f, die jedem Knoten \(v\) seinen Grad \(\deg (v)\) zuordnet und verwende das Schubfachprinzip.

Problem: Wir habe, sagen wir, n Knoten, dann sind die Grade \(0, \ldots n-1\) möglich, also n mögliche Bilder. Tatsächlich aber kann es in einem Graph nicht gleichzeitig einen Knoten mit Grad 0 und einen Knoten mit Grad n-1 geben. Also ist für jeden Graph die Zahl der möglichen Bilder von f kleiner als n.

Gruß