Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad

01.02.2019, 19:15

Slexout

Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad

Meine Frage:
Siehe Anhang für die Fragestellung

Meine Ideen:
Hallo,

ich hätte eine Beweisaufgabe zur Graphentheorie, zu welcher ich bereits ein Widerspruchsbeweis aufgestellt habe. Ich bin mir nur nicht sicher, ob das so korrekt ist und frage mich ob ich das anhand Formeln besser formulieren könnte.

Die Aufgabenstellung ist die folgende:

Sei $\begin{eqnarray*} G = (V, E) \end{eqnarray*}$ ein (einfacher, endlicher, ungerichteter) Graph. Beweisen sie folgende Aussage:

Gilt $\begin{eqnarray*} |V| \geq 2 \end{eqnarray*}$ , so existieren zwei Knoten $\begin{eqnarray*} v_1, v_2 \in V, v_1 \neq v_2 \end{eqnarray*}$ mit gleichem Grad $\begin{eqnarray*} deg(v_1) = deg(v_2) \end{eqnarray*}$

Ich möchte nun, wie im Hinweis erwähnt, ein Widerspruchsbeweis durchführen. Dafür nehme ich folgendes an:

Gilt $\begin{eqnarray*} |V| \geq 2 \end{eqnarray*}$ , so haben alle Knoten einen unterschiedlichen Grad.

Beweis:

Angenommen es existieren n Knoten zu denen jeder $\begin{eqnarray*} {0, ..., n-1} \end{eqnarray*}$ ausgehende Kanten (Grad) haben kann.

Da nun jeder Knoten zwangsweise einen unterschiedlichen Grad haben muss, müssen die Knoten folgende Gradzahl haben:

1. Knoten - 0 Grad bzw. 0 ausgehende Kanten
2. Knoten - 1 Grad
3. Knoten - 2 Grad

...

n. Knoten - (n-1) Grad.

Damit hat jeder Knoten unterschiedliche Grade.

Da nun der n.te Knoten (n-1) ausgehende Kanten hat (welche mit anderen Knoten verbunden sein müssen) und wir nur n Elemente zur Verfügung haben, muss dieser Knoten zwangsweise mit dem 1.ten Knoten (welcher 0 Kanten hat) verbunden sein.

Somit ist das ein Widerspruch und unsere Annahnme war falsch. Somit müssen 2 Knoten in einem Graphen existieren, welche die selbe Gradzahl haben.

Nun zu meiner Frage:

Reicht das als Beweis ? Oder muss ich noch irgendwie zeigen, dass nun der Knoten den selben Grad hat wie ein anderer?
Desweiteren würde ich gerne noch irgendwelche Formeln mit ins Spiel bringen, ich habe bis jetzt ja alles ziemlich textuell beschrieben. Jedoch weiß ich auch nicht wie man das mit Formeln lösen könnte. Da ich ja immer den Nachfolger betrachte müsste doch ein Induktionsbeweis möglich sein.

Vielen Dank im Voraus.

Viele Grüße
Slexout

Edit: Latex

01.02.2019, 20:16

URL

Auf diesen Beitrag antworten »

RE: Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad
Ich würde sagen, das reicht.
Allerdings würde ich dein Argument nicht als Widerspruchsbeweis aufziehen:
n Knoten, also mögliche Grade 0,1,..n-1
Es gibt einen Knoten mit Grad n-1: Graph ist ein Stern, die äußeren Knoten haben alle Grad 1
Grad n-1 kommt nicht vor: dann gibt es nur n-1 mögliche Grade für die n Knoten. Schubfachprinzip sagt, ein Grad muss doppelt vorkommen.

01.02.2019, 20:39

Slexout

Auf diesen Beitrag antworten »

Hey URL,

danke dir für deine Antwort!

Zitat:

Allerdings würde ich dein Argument nicht als Widerspruchsbeweis aufziehen

Wieso nicht?

Zitat:

Grad n-1 kommt nicht vor: dann gibt es nur n-1 mögliche Grade für die n Knoten.

Wie meinst du das?

Viele Grüße
Slexout

01.02.2019, 20:42

URL

Auf diesen Beitrag antworten »

Weil ich es bevorzuge, Dinge ohne Widerspruch zu beweisen, wenn es anders geht. Persönliche Vorliebe.
Wenn kein Knoten den Grad n-1 hat, können nur die Grade 0,1,...,n-2 vorkommen.

01.02.2019, 21:03

Slexout

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Weil ich es bevorzuge, Dinge ohne Widerspruch zu beweisen, wenn es anders geht. Persönliche Vorliebe.
Wenn kein Knoten den Grad n-1 hat, können nur die Grade 0,1,...,n-2 vorkommen.

Ok, aber es gibt keine Einwände zu meinem Beweis ? Big Laugh

Wenn nicht würde ich den so lassen, denn im Hinweis steht wir sollen am besten einen Widerspruchsbeweis nutzen.

01.02.2019, 21:05

URL

Auf diesen Beitrag antworten »

RE: Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad
Wie ich schon eingangs feststellte

Zitat:

Original von URL
Ich würde sagen, das reicht.

01.02.2019, 21:15

Slexout

Auf diesen Beitrag antworten »

RE: Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad
Gut, danke dir Freude

02.02.2019, 01:48

10001000Nick1

Auf diesen Beitrag antworten »

RE: Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad

Zitat:

Original von URL
Es gibt einen Knoten mit Grad n-1: Graph ist ein Stern, die äußeren Knoten haben alle Grad 1

Wieso genau Grad 1? Die äußeren Knoten können doch auch noch durch Kanten verbunden sein. Richtig ist, wie Slexout schon geschrieben hat, dass die äußeren Knoten mind. Grad 1 haben, und damit gibt es wieder mit dem Schubfachprinzip zwei Knoten mit demselben Grad.

02.02.2019, 09:50

URL

Auf diesen Beitrag antworten »

RE: Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad
Danke 10001000Nick1, du hast natürlich vollkommen recht Wink

Neue Frage »

Antworten »

Beweisaufgabe Graphentheorie: Es existieren zwei Knoten mit selben Grad

Verwandte Themen