Mostre que todo grafo conexo planar possui um nó com grau menor do que ou igual a cinco.
Passo 1
O enunciado pede para mostrar que em qualquer grafo planar conexo existe pelo menos um vértice de grau menor ou igual a cinco. O conteúdo que vamos usar é a fórmula de Euler para grafos planares conexos
onde
é o número de vértices,
o número de arestas e
o número de faces, além do fato que cada face é delimitada por pelo menos três arestas.
Passo 2
Em todo grafo planar conexo, somando os graus de todas as faces contamos cada aresta duas vezes, logo
e daí
Substituindo esse valor de
na fórmula de Euler, obtemos
Passo 3
O grau médio
dos vértices é dado por
para
. Como a média dos graus é estritamente menor que
, não é possível que todos os vértices tenham grau
. Logo, existe pelo menos um vértice de grau
.
Resposta
Todo grafo conexo planar possui pelo menos um nó com grau menor ou igual a cinco.