Das Problem ist nicht lösbar.
Es gibt zwei
nicht planare "Grundgraphen", die gern zur Untersuchung der Planarität von Graphen verwendet werden, nämlich den K3,3 und den K5 (Pentagramm).
Planar bedeutet, dass es zum Graphen G einen
isomorphen Graphen G' gibt, bei dem sich keine Kanten überschneiden.
Dieses Problem entspricht dem K3,3.
Dass die beiden Graphen nicht planar sind, kann man natürlich beweisen.
Dazu brauchen wir aber und noch ein paar Sätze.
(Um "daraus folgt" von "größer gleich" und "kleiner gleich" unterscheiden zu können werde ich "->" dafür verwenden)
Fangen wir mit der Eulerschen Polyederformel an:
Sei G ein zusammenhängender ebener Graph mit n Ecken, m Kanten und f Gebieten n,m,f
Є N.
Dann gilt:
n + f = m + 2
Den Satz kannst du mit vollständiger Induktion beweisen, was wir uns hier jetzt aber mal sparen!
Ebenso gilt für einen planaren, zusammenhängenden Graphen mit n Ecken und m Kanten:
m <= 3*n - 6.
Beweis:
G ist isomorph zu einem planaren Graph G'. G' hat ebenfalls n Ecken und m Kanten. Die Anzahl der Gebiete in G' sei f. In G' wird jedes Gebiet durch mindestens drei Kanten begrenzt. Jede Kante liegt zwischen genau zwei Gebieten. Also ist 3*f <= 2*m
Mit der Formel von Euler ergibt das:
n + f = m + 2 -> m = n + f - 2 -> m <= n + 2/3*m - 2 -> 1/3*m <= n - 2 -> m <= 3*n - 6.
OK, damit können wir schon beweisen, dass der K5 nicht planar sein kann:
Angenommen der K5 sei planar.
So muss gelten, dass m <= 3*n - 6.
Der K5 hat genau 5 Ecken und 10 Kanten, also ist 10 <= 3*5 - 6 = 9, was im Widerspruch zur Annahmen steht, dass der K5 planar ist.
Für den K3,3 geht das so direkt leider nicht.
Dazu brauchen wir noch folgenden Satz:
Sei G ein zusammenhängender planarer Graph ist mit n Ecken und m Kanten, ohne Dreiecke.
Dann gilt:
m <= 2*n - 4
Beweis:
G' ist also eine planare Darstellung (von G) mit f Gebieten. Da der Grad jedes Gebietes eines Graphen ohne Dreiecke mindesten 4 beträgt, folgt, dass 2*m >= 4*f.
Eingesetzt in die Polyederformel ergibt das:
m - n + 2 <= 1/2 * m -> m <= 2*n - 4
Nun können wir beweisen, dass der K3,3 nicht planar ist.
Nehmen wir also an der K3,3 sei planar.
Da der K3,3 keine Dreiecke hat, muss gelten:
m <= 2*n - 4
Der K3,3 hat 6 Ecken und 9 Kanten, also:
9 <= 2*6 - 4 = 8
Dies steht im Widerspruch zur Annahme, der K3,3 ist also nicht planar.
Das war's!
Gruß,
Schwinni
