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

$K_5$ sei der vollständige Graph mit 5 Knoten. Zeigen Sie mithilfe der Eulerschen Polyederformel,

dass $K_5$ nicht planar ist.

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
}}

Lösungsvorschlag

Für planare Graphen gilt die Eulersche Polyederformel, die wie folgt lautet:

${\alpha }_2=2+{\alpha }_1-{\alpha }_0$

${\alpha }_0$ ist die Anzahl der Knoten

${\alpha }_1$ ist die Anzahl der Kanten

${\alpha }_2$ ist die Anzahl der Gebiete

Falls $K_5$ planar ist, besitzt der Graph:

5 Knoten

10 Kanten (jeden Knoten mit jedem anderen Knoten verbinden)

7 Gebiete (lässt sich mit der Eulerschen Polyederformel ausrechnen)

Nun wissen wir aber, dass die Abgrenzung eines Gebietes mindestens 3 Kanten benötigt und dass jede Kante zu zwei Gebieten gehört. Damit stellen wir folgende Ungleichung auf.

$2{\alpha }_1\ge 3{\alpha }_2$

Setzen wir die Werte von $K_5$ ein, erhalten wir:

$2\ast 10\ge 3\ast 7$

$20\ge 21$

und haben somit einen Widerspruch. Also kann $K_5$ nicht planar sein.

Achtung:

Diese Ungleichung funktioniert i. A. nicht, da man auf diese Weise auch beweisen könnte, dass $K_2$ nicht planar ist.