Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 rokuKazimierz Kuratowski: Sur the problème des courbes gauches en Topologie. Fundamenta Mathematicae 15 (1930) ss. 271–283.
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 (graf pełny o pięciu wierzchołkach) lub (graf pełny dwudzielny o sześciu wierzchołkach, z których trzy są połączone z każdym z pozostałych trzech).
Zobacz też domki i studnie
Przypisy
Bibliografia Frank Harary, Graph Theory. Addison-Wesley, Reading 1969, s. 133
Linki zewnętrzne
Kuratowskiego