Mostre que
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.)
(Sugestão: Considere o ciclo formado pelos seis nós.)
Passo 1
Estamos diante do grafo completo bipartido
, com partes
e
, total de
vértices e
arestas. Vamos mostrar que
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
que passa alternadamente por vértices das duas partes. Por exemplo,
Esse
é um ciclo simples que usa exatamente 6 das 9 arestas de
.
Suponha, por contradição, que seja planar. Então podemos desenhar
como um ciclo Jordan no plano, o qual separa o plano em uma região interna e outra externa. Restam exatamente
arestas de
fora de
, são elas
Suponha, por contradição, que
Passo 3
Cada uma das arestas
,
e
tem seus dois extremos em vértices de
. Observamos que, ao percorrer o ciclo
na ordem indicada, os dois extremos de cada uma dessas arestas estão separados por um número ímpar de arestas de
. 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
um número ímpar de vezes, concluímos que cada uma de
,
,
cruza o ciclo
um número ímpar de vezes.
Logo, o total de interseções entre as arestas extras e as arestas de é soma de três números ímpares, isto é, ímpar. Todas essas interseções ocorrem em pontos interiores às arestas de
. Como
tem 6 arestas, pelo princípio da casa dos pombos haverá pelo menos uma aresta de
que é cruzada por um número ímpar de arestas extras — no mínimo duas delas devem cruzar o mesmo segmento de
. Essas duas arestas extras, ao batalharem pelo mesmo cruzamento no mesmo trecho de
, obrigam-se a cruzar-se mutuamente, gerando uma intersecção entre duas arestas de
. Isso é impossível em um desenho planar.
Logo, o total de interseções entre as arestas extras e as arestas de
Passo 4
Chegamos a uma contradição com a hipótese de planaridade. Portanto,
não é planar.