Aufgabe:
Gegeben sei ein ungerichteter Graph mit Adjazenzmatrix (liegt mir vor). Zeigen Sie, dass der Graph nicht planar ist.
Problem/Ansatz:
Eulersche Polyederformel funktioniert leider nicht, denn mein Graph hat 20 Kanten und 9 Knoten, also |E| <= 3|V|-6 wäre dann ja 20 <= 3x9-6 und demnach 20 <= 21, was ja bekanntlich wahr ist. Also keine Aussage bezüglich Nichtplanarität.
Mir ist der Satz von Kuratowski bekannt, und dass ich nachweisen muss, dass K5 oder K3,3 im Graph existieren. Bei 9 Knoten und 20 Kanten kann ich leider nicht deuten, welche Knoten / Kanten ich zusammenfügen / entfernen / löschen soll. Wie ist dies anhand der Matrix möglich, ohne den Graph aufzuzeichnen? Wäre über Hilfe sehr dankbar. :)
