TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 308

Man zeige, dass es in einem Graphen $G$ mit $0<\alpha _{1}(G)<\alpha _{0}(G)$ immer einen Knoten $v\in V(G)$ mit $d(v)<=1$ gibt.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

• $\alpha _{0}(G)=|V(G)|$ ... Anzahl der Knoten
• $\alpha _{1}(G)=|E(G)|$ ... Anzahl der Kanten

Handschlaglemma

Handschlaglemma

In einem einfachen Graphen G gilt: $\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$ Die Summe der Knotengrade ist genau doppelt so groß wie die Anzahl der Kanten.

Lösungsvorschlag

Es gilt also zu zeigen, dass in einem Graphen, in dem die Anzahl der Kanten kleiner als die Anzahl der Knoten ist, immer ein Knoten den Grad 0 oder 1 hat. Ein Knoten ist somit isoliert oder hat nur eine Kante. Am einfachsten lässt sich das mit einem Beweis durch Widerspruch und dem Handschlaglemma zeigen.

Für den Beweis nehmen wir also an, dass das Gegenteil gilt, nämlich dass es keinen Knoten mit Grad $<=1$ gibt, d.h. alle Knotengrade $d(v)>1$ sind.

Das Handschlaglemma stellt eine Verbindung zwischen der Summe der Grade der Knoten und der Anzahl der Kanten her:

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$

Die Summe auf der linken Seite zählt alle Knotengrade zusammen. In diesem Fall wäre $d(v)$ gemäß unserer Definition also für jeden Knoten mindestens $2$, also ist die Summe auch mindestens $2\cdot |V(G)|$. Deshalb können wir o. B. d. A. sagen, dass

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|>=2\cdot |V(G)|$

Somit können wir auch schreiben:

$2\cdot |E(G)|>=2\cdot |V(G)|\Rightarrow |E(G)|>=|V(G)|\Rightarrow \alpha _{1}(G)>=\alpha _{0}(G)$

Das heißt also, dass die Anzahl der Kanten größer oder gleich der Anzahl der Knoten ist (wenn alle Grade mindestens 2 sind). Somit haben wir unseren Beweis erbracht. Damit gilt auch automatisch der Umkehrschluss:

Ein Graph $G$ hat immer einen Knoten $v\in V(G)$ mit $d(v)<=1$, wenn $0<\alpha _{1}(G)<\alpha _{0}(G)$ gilt.