Mostre que
não é planar usando a desigualdade obtida no corolário 8.6.
Passo 1
O enunciado pede para mostrar que o grafo completo
não é planar usando o corolário 8.6. O assunto é teoria de grafos planares e vamos precisar do resultado que dá um limite superior para o número de arestas de um grafo simples e planar em função do número de vértices.
Passo 2
Corolário 8.6: Se
é um grafo simples e planar com
vértices e
arestas, então vale a desigualdade
Passo 3
No caso de
, como é o grafo completo em 5 vértices, temos
Passo 4
Vamos testar a desigualdade do corolário em
:
Mas isso dá
, o que é falso. Logo
não satisfaz a condição necessária para ser planar.