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

$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}\geq 3\alpha _{2}$

Setzen wir die Werte von $K_{5}$ ein, erhalten wir:

$2*10\geq 3*7$

$20\geq 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.