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
n - m + f = 2,
onde n é o número de vértices, m o número de arestas e f 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
2m \;=\;\sum_{\text{faces }F}\deg(F)\;\ge\;3f
e daí
f \le \frac{2m}{3}.
Substituindo esse valor de f na fórmula de Euler, obtemos
n - m + \frac{2m}{3} \;\ge\;2 \quad\Longrightarrow\quad n - \frac{m}{3} \;\ge\;2 \quad\Longrightarrow\quad m \le 3n - 6.

Passo 3

O grau médio \bar d dos vértices é dado por
\bar d \;=\;\frac{2m}{n} \;\le\; \frac{2(3n-6)}{n} \;=\; 6 - \frac{12}{n} \;<\;6,
para n\ge3. Como a média dos graus é estritamente menor que 6, não é possível que todos os vértices tenham grau \ge6. Logo, existe pelo menos um vértice de grau \le5.

Resposta

Todo grafo conexo planar possui pelo menos um nó com grau menor ou igual a cinco.

Exercícios de Livros Relacionados