Na teoria dos grafos, o teorema de Kuratowski é um teorema que permite caracterizar os grafos planares, publicado em 1930 por Kazimierz Kuratowski^[1]. O teorema declara que um grafo finito^[2] é planar se, e somente se, ele não contém nenhum subgrafo que seja uma subdivisão de ${\displaystyle K_{5}}$ (o grafo completo com cinco vértices) ou de ${\displaystyle 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 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 ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3,3}}$;
• se o grafo não tiver nenhum subgrafo que seja uma subidivisão de ${\displaystyle K_{5}}$ ou ${\displaystyle 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 ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3,3}}$

Um grafo planar é um grafo que pode ser desenhado no plano sem que as suas arestas se intersetem. Um subgrafo de um grafo ${\displaystyle G}$ é um grafo cujos vértices e arestas são um subconjunto dos vértices e arestas de ${\displaystyle G}$. Uma subdivisão de um grafo é um novo grafo formado ao subdividir uma aresta desse grafo (basicamente colocar mais vértices numa aresta).

O teorema foi publicado por Kazimierz Kuratowski em 1930. Também em 1930 foi provado independentemente por Orrin Frink e Paul Smith^[3], 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.^[4] Desde então, várias novas provas deste teorema têm sido descobertas^[5].

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

• Grafo planar

Referências

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e