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ß