gibt die wohl berühmteste Charakterisierung planarer Graphen an und wurde 1930 von K. Kuratowski gefunden.

Ein Graph G ist genau dann planar, wenn er keinen zum vollständigen GraphenK₅oder vollständigen bipartiten Graphen K_3,3homöomorphen Graphen alsTeilgraphen besitzt.

Aus der Euler-Poincaréschen Formel folgt leicht, daß der K₅ und der K_3,3 selbst keine planaren Graphen sein können. Nach dieser dürfte der K₅ als Graph mit 5 Ecken höchstens 3 · 5 − 6 = 9 und nicht 10 Kanten besitzen, und der K_3,3 dürfte als Graph mit Taillenweite 4 und 6 Ecken höchstens 2 · 6 − 4 = 8 und nicht 9 Kanten besitzen.

Die Bedingung des Satzes von Kuratowski kann man äquivalent ebenfalls so formulieren, daß G we-der den K₅ noch den K_3,3 als Minor besitzt (Minor eines Graphen). Gerade in dieser zweiten Formulierung ist der Satz von Kuratowski der klassische Prototyp für Charakterisierungen einer Eigenschaft von Graphen mittels verbotener Minoren.