Teorema de Kuratowski

Na teoria dos grafos, o teorema de Kuratowski é um teorema que permite caracterizar os grafos planares, publicado em 1930 por Kazimierz Kuratowski. O teorema declara que um grafo finito é planar se, e somente se, ele não contém nenhum subgrafo que seja uma subdivisão de $K_5$ (o grafo completo com cinco vértices) ou de $K_{3,3}$ (grafo bipartido completo com seis vértices, três dos quais se conectam a cada um dos outros três), também conhecido como o gráfico de utilidade.

O teorema

$K_5$ - O grafo completo com 5 vértices. (Todos os vértices estão ligados entre si).

Enunciado do teorema

O teorema apresenta uma condição necessária e suficiente para a planaridade, logo consiste em duas implicações:

• se o grafo for planar, então não tem nenhum subgrafo que seja uma subdivisão de $K_5$ ou $K_{3,3}$;
• se o grafo não tiver nenhum subgrafo que seja uma subidivisão de $K_5$ ou $K_{3,3}$, então é planar.

Alternativamente, uma versão equivalente é que um grafo é não-planar se e só se contém um subgrafo que é uma subidivsão de $K_5$ ou $K_{3,3}$

Algumas definições

$K_{3,3}$- Grafo bipartido completo com 6 vértices. Existem dois conjuntos de 3 vértices em que cada um dos vértices está ligados a todos os vértices do outro conjunto.

Um grafo planar é um grafo que pode ser desenhado no plano sem que as suas arestas se intersetem. Um subgrafo de um grafo

$G$

é um grafo cujos vértices e arestas são um subconjunto dos vértices e arestas de

$G$

. Uma subdivisão de um grafo é um novo grafo formado ao subdividir uma aresta desse grafo (basicamente colocar mais vértices numa aresta).

História

O teorema foi publicado por Kazimierz Kuratowski em 1930. Também em 1930 foi provado independentemente por Orrin Frink e Paul Smith, contudo a sua prova nunca foi publicada. O caso particular de grafos planares cúbicos também foi provado independentemente por Karl Menger em 1930. Desde então, várias novas provas deste teorema têm sido descobertas.

Na união soviética, este teorema era conhecido como o teorema de Pontryagin-Kuratowski ou Kuratowski-Pontryagin, já que teria sido provado por Lev Pontryagin por volta de 1927. Contudo, como Pontryagin nunca publicou a sua prova, este nome não se espalhou.

Ver também

• Grafo planar