Mostre que um grafo planar com 4 ou mais nós tem pelo menos 4 nós de grau menor do que ou igual a 5.
(Sugestão: utilize indução.)

Passo 1

Vamos provar que todo grafo planar simples G com n\ge4 vértices tem pelo menos quatro vértices de grau \le5. Para isso, usaremos o fato de que, ao “completar” G até uma triangulação maximal T, os graus só aumentam, e em T podemos aplicar a fórmula de Euler para somas de graus.

Passo 2

Aumente G até um grafo planar maximal T (ou seja, uma triangulação) adicionando arestas entre vértices não adjacentes sempre que possível. Como T é maximal e planar, cada face de T é um triângulo. Denotemos por V o número de vértices de T (que é o mesmo de G) e por E o número de arestas de T.
Pela fórmula de Euler para grafos planares, temos
V - E + F = 2
e como em uma triangulação cada face tem 3 arestas e cada aresta pertence a duas faces, segue
3F = 2E.
Daí
F = \frac{2E}{3} \quad\Longrightarrow\quad V - E + \frac{2E}{3} = 2 \;\Longrightarrow\; E = 3V - 6.

Passo 3

Em T, a soma dos graus dos vértices é
\sum_{v\in V(T)}\deg_T(v) \;=\; 2E \;=\; 2(3V-6) \;=\; 6V - 12.
Reescrevendo,
\sum_{v\in V(T)}\bigl(6 - \deg_T(v)\bigr) \;=\; \sum_{v}6 \;-\; \sum_{v}\deg_T(v) \;=\; 6V \;-\;(6V-12) \;=\; 12.
Agora note que apenas vértices de grau \le5 contribuem com termo positivo em (6-\deg_T(v)). Além disso, em toda triangulação simples vale \deg_T(v)\ge3, logo para cada vértice de grau \le5 temos
6 - \deg_T(v)\;\le\;6-3=3.
Sejam S\subseteq V(T) os vértices tais que \deg_T(v)\le5. Então
\sum_{v\in S}\bigl(6-\deg_T(v)\bigr)\;\le\;\sum_{v\in S}3 \;=\; 3\,|S|.
Mas como toda a soma sobre todos os vértices é 12 e os demais (aqueles de grau \ge6) contribuem com valores não positivos, segue
3\,|S|\;\ge\;12 \quad\Longrightarrow\quad |S|\;\ge\;4.
Portanto a triangulação T tem pelo menos quatro vértices de grau \le5.

Passo 4

Por construção, T é obtido a partir de G apenas adicionando arestas, de modo que para cada vértice v vale
\deg_G(v)\;\le\;\deg_T(v).
Assim, aqueles quatro vértices de T com \deg_T(v)\le5 satisfazem também \deg_G(v)\le5. Concluímos que G tinha ao menos quatro vértices de grau \le5.

Resposta

Todo grafo planar simples com n\ge4 vértices tem pelo menos quatro vértices de grau menor ou igual a 5.

Exercícios de Livros Relacionados