TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 303

Aus VoWi
Zur Navigation springen Zur Suche springen

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.

Hilfreiches[Bearbeiten]

  • \alpha_0(G) = | V(G) | ... Anzahl der Knoten
  • \alpha_1(G) = | E(G) | ... Anzahl der Kanten
Handschlaglemma
Handschlaglemma[Bearbeiten, WP, 2.13 Satz]

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[Bearbeiten]

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 Kantengrade 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.