TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 314
sei der vollständige Graph mit 5 Knoten. Zeigen Sie mithilfe der Eulerschen Polyederformel,
dass nicht planar ist.
{{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.