TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 309

Aus VoWi
Zur Navigation springen Zur Suche springen

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

dass K_5 nicht planar ist.

Lösungsvorschlag[Bearbeiten]

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*10 \ge 3*7

 20 \ge 21

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


Achtung:[Bearbeiten]

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