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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige, dass es in einem Graphen mit immer einen Knoten mit 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[Bearbeiten | Quelltext bearbeiten]

  • ... Anzahl der Knoten
  • ... Anzahl der Kanten
Handschlaglemma
Handschlaglemma[Bearbeiten, Wikipedia, 2.13 Satz]

In einem einfachen Graphen G gilt: Die Summe der Knotengrade ist genau doppelt so groß wie die Anzahl der Kanten.

Lösungsvorschlag[Bearbeiten | Quelltext 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 gibt, d.h. alle Knotengrade sind.

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

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

Somit können wir auch schreiben:

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 hat immer einen Knoten mit , wenn gilt.