Twierdzenie Kuratowskiego

Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku^[1].

Uwagi

Przez rozszerzenie grafu rozumiemy "wstawianie wierzchołka do krawędzi", tj. rozerwanie krawędzi między dwoma wierzchołkami, dodanie kolejnego wierzchołka i połączenia wierzchołków pierwotnych poprzez właśnie dodany wierzchołek. Grafem rozszerzonym nazwiemy graf powstały z danego poprzez co najmniej jednokrotne rozszerzenie grafu.

Teza

Skończony graf jest planarny (spłaszczalny), jeśli nie zawiera podgrafu, który jest grafem rozszerzonym grafu ${\displaystyle K_{5}}$ (graf pełny o pięciu wierzchołkach) lub ${\displaystyle K_{3,3}}$ (graf pełny dwudzielny o sześciu wierzchołkach, z których trzy są połączone z każdym z pozostałych trzech)^[2].

• 
  K5
• 
  K 3,3

Zobacz też

• domki i studnie

Przypisy

Bibliografia

• Frank Harary, Graph Theory. Addison-Wesley, Reading 1969, s. 133

Linki zewnętrzne

• Planar Graphs, [w:] Numberphile [online], YouTube, 11 listopada 2019 [dostęp 2019-11-12]  (ang.).