Mostre que K_{5} não é planar usando a desigualdade obtida no corolário 8.6.

Passo 1

O enunciado pede para mostrar que o grafo completo K_5 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 G é um grafo simples e planar com n\ge3 vértices e m arestas, então vale a desigualdade
m \le 3n - 6.

Passo 3

No caso de K_5, como é o grafo completo em 5 vértices, temos
n = 5 \quad\text{e}\quad m = \binom{5}{2} = 10.

Passo 4

Vamos testar a desigualdade do corolário em K_5:
m \le 3n - 6 \quad\Longrightarrow\quad 10 \le 3\cdot5 - 6 = 9.
Mas isso dá 10 \le 9, o que é falso. Logo K_5 não satisfaz a condição necessária para ser planar.

Resposta

K_5 não é planar.

Exercícios de Livros Relacionados