Teorema de Kuratowski
Dizemos que um grafo $G = (V,A)$ é uma subdivisão de um grafo $H = (V',A')$ se $G$ é construído a partir da remoção de uma quantidade finita de arestas de $H$ e a substituição de cada uma dessas arestas por caminhos conectando seus vértices.
No exemplo abaixo, o grafo $G$ é uma subdivisão do grafo $H$.
1 Desenhe um grafo do qual o grafo $H$ acima é uma subdivisão.
2 Mostre que um grafo é planar se, e somente se, todas as suas subdivisões são planares.
O Teorema de Kuratowski nos diz que um grafo com uma quantidade finita de vértices é planar se, e somente se, não possui uma subdivisão de $K_{3,3}$ ou $K_5$ como subgrafo. Já sabemos que, se tal grafo é planar, não pode conter uma subdivisão de $K_{3,3}$ ou $K_5$ como subgrafo. No roteiro abaixo, concluiremos a recíproca.
Dado $G=(V,A)$ um grafo conexo, um vértice de corte de $G$ é um vértice $v\in V$ tal que o subgrafo induzido a $V\setminus \{v\}$ é desconexo. Isto é, $v$ é um vértice cuja remoção “aumenta” a quantidade de componentes conexas do grafo. Um bloco de $G$ é um subgrafo conexo maximal $H$ de $G$ que não possui um vértice de corte, isto é, se $H'$ é um subgrafo conexo de $G$ que não possui vértices de corte e $H$ é subgrafo de $H'$, então $H=H'$.
No exemplo abaixo, temos um grafo $G$ e seus blocos representados logo abaixo.
3 Seja $G = (V,A)$ um grafo conexo que não possui vértices de corte e fixe $u,v \in V$. Por indução sobre $d(u,v)$, mostre que existe um ciclo de $G$ contendo $u$ e $v$ como vértices.
4 Mostre que todo vértice de um grafo $G$ é vértice de algum bloco de $G$.
5 Seja $G$ um grafo e $H$ e $H'$ dois de seus blocos distintos. Mostre que os vértices de $H$ e os vértices de $H'$ se intersectam em no máximo um vértice.
6 Seja $G$ um grafo com finitos vértices e pelo menos dois blocos distintos. Considere $C$ o conjunto de seus vértices de corte e $B$ o conjunto de seus blocos. Vamos construir um grafo $T$ com conjunto de vértices $C\cup B$. Uma aresta $\{c,b\}$ existe se, e somente se, $c \in C$, $b \in B$ e o bloco $b$ contém o vértice de corte $c$.
6.1 Mostre que $T$ não possui circuitos como subgrafos.
6.2 Conclua que $G$ possui um bloco que contém apenas um vértice de corte de $G$.
7 Mostre que, se $G$ é um grafo com uma quantidade finita de vértices e todos os seus blocos são planares, então $G$ é planar.
7.1 Conclua que $G$ é um grafo planar se, e somente se, todos os seus blocos são planares.
Agora, o Teorema de Kuratowski se resume a mostrar que, se $G$ é um grafo que não possui vértices de corte e nem subdivisão de $K_{3,3}$ ou $K_5$, então $G$ é planar.
8 Por um momento, suponha que o Teorema de Kuratowski é falso e considere $G = (V,A)$ um grafo com finitos vértices que não possui vértices de corte e nem subdivisão de $K_{3,3}$ ou $K_5$. Podemos supor que $G$ possui a mínima quantidade de vértices com esta propriedade, isto é, qualquer grafo com menos vértices do que $G$ possuirá uma representação planar.
8.1 Observe que $\delta(G)\geq 2$. Mostre que, ainda mais, $\delta(G)\geq 3$.
8.2 Mostre que existe uma aresta $a \in A$ tal que o grafo $G = (V,A\setminus \{a\})$ também não possui vértices de corte.