(Satz von Kuratowski) Ein Graph G ist planar genau dann, wenn er keine Unterteilungen des K5 oder des K3,3 als Teilgraphen enthält.
Dass das angegebene Kriterium hinreichend ist, ist weitaus schwerer zu zeigen als die Notwendigkeit, die wir ja ohne größere Mühe oben haben erklären können. Im Rahmen der Vorlesung können wir daher keinen vollständigen Beweis des Satzes von Kuratowski geben. Es sei etwa verwiesen auf:
Martin Aigner, Graphentheorie, Kapitel 4, Teubner, 1984.
Grad im Netz gefunden.. aber ne klar, Hummi hats gecheckt
Wir habens übrigens in der VO auch nicht bewiesen..
Zitat 
