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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

dass 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[Bearbeiten | Quelltext bearbeiten]

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

ist die Anzahl der Knoten

ist die Anzahl der Kanten

ist die Anzahl der Gebiete

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

Setzen wir die Werte von ein, erhalten wir:

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


Achtung:[Bearbeiten | Quelltext bearbeiten]

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