Mostre que K_{3,3} não é planar usando método análogo ao da segunda demonstração do corolário 8.7.
(Sugestão: Considere o ciclo formado pelos seis nós.)

Passo 1

Estamos diante do grafo completo bipartido K_{3,3}, com partes \{a,b,c\} e \{1,2,3\}, total de 6 vértices e 9 arestas. Vamos mostrar que K_{3,3} não admite desenho planar usando um argumento análogo ao da segunda demonstração do Corolário 8.7, que explora o Teorema de Jordan e contagem de interseções com um ciclo simples.

Passo 2

Escolhemos o ciclo de comprimento 6 em K_{3,3} que passa alternadamente por vértices das duas partes. Por exemplo,
C = a \;-\; 1 \;-\; b \;-\; 2 \;-\; c \;-\; 3 \;-\; a.
Esse C é um ciclo simples que usa exatamente 6 das 9 arestas de K_{3,3}.
Suponha, por contradição, que K_{3,3} seja planar. Então podemos desenhar C como um ciclo Jordan no plano, o qual separa o plano em uma região interna e outra externa. Restam exatamente 3 arestas de K_{3,3} fora de C, são elas
a2,\quad b3,\quad c1.

Passo 3

Cada uma das arestas a2, b3 e c1 tem seus dois extremos em vértices de C. Observamos que, ao percorrer o ciclo C na ordem indicada, os dois extremos de cada uma dessas arestas estão separados por um número ímpar de arestas de C. Pelo Teorema de Jordan, para ligar dois pontos distintos do ciclo sem sair da mesma região (interna ou externa), a curva ligadora deve cruzar o ciclo um número par de vezes; para ficar do outro lado, cruza um número ímpar de vezes. Como cada aresta extra não pode entrar e sair da mesma região sem cruzar C um número ímpar de vezes, concluímos que cada uma de a2, b3, c1 cruza o ciclo C um número ímpar de vezes.
Logo, o total de interseções entre as arestas extras e as arestas de C é soma de três números ímpares, isto é, ímpar. Todas essas interseções ocorrem em pontos interiores às arestas de C. Como C tem 6 arestas, pelo princípio da casa dos pombos haverá pelo menos uma aresta de C que é cruzada por um número ímpar de arestas extras — no mínimo duas delas devem cruzar o mesmo segmento de C. Essas duas arestas extras, ao batalharem pelo mesmo cruzamento no mesmo trecho de C, obrigam-se a cruzar-se mutuamente, gerando uma intersecção entre duas arestas de K_{3,3}. Isso é impossível em um desenho planar.

Passo 4

Chegamos a uma contradição com a hipótese de planaridade. Portanto, K_{3,3} não é planar.

Resposta

K_{3,3} não é planar.

Exercícios de Livros Relacionados