Direkt zum Inhalt

Lexikon der Mathematik: Kuratowski, Satz von

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 Graphen K5oder vollständigen bipartiten Graphen K3,3homöomorphen Graphen als Teilgraphen besitzt.

Aus der Euler-Poincaréschen Formel folgt leicht, daß der K5 und der K3,3 selbst keine planaren Graphen sein können. Nach dieser dürfte der K5 als Graph mit 5 Ecken höchstens 3 · 5 − 6 = 9 und nicht 10 Kanten besitzen, und der K3,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 K5 noch den K3,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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos