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.)
(Sugestão: utilize indução.)
Passo 1
Vamos provar que todo grafo planar simples
com
vértices tem pelo menos quatro vértices de grau
. Para isso, usaremos o fato de que, ao “completar”
até uma triangulação maximal
, os graus só aumentam, e em
podemos aplicar a fórmula de Euler para somas de graus.
Passo 2
Aumente
até um grafo planar maximal
(ou seja, uma triangulação) adicionando arestas entre vértices não adjacentes sempre que possível. Como
é maximal e planar, cada face de
é um triângulo. Denotemos por
o número de vértices de
(que é o mesmo de
) e por
o número de arestas de
.
Pela fórmula de Euler para grafos planares, temos
e como em uma triangulação cada face tem 3 arestas e cada aresta pertence a duas faces, segue
Daí
Passo 3
Em
, a soma dos graus dos vértices é
Reescrevendo,
Agora note que apenas vértices de grau
contribuem com termo positivo em
. Além disso, em toda triangulação simples vale
, logo para cada vértice de grau
temos
Sejam
os vértices tais que
. Então
Mas como toda a soma sobre todos os vértices é 12 e os demais (aqueles de grau
) contribuem com valores não positivos, segue
Portanto a triangulação
tem pelo menos quatro vértices de grau
.
Passo 4
Por construção,
é obtido a partir de
apenas adicionando arestas, de modo que para cada vértice
vale
Assim, aqueles quatro vértices de
com
satisfazem também
. Concluímos que
tinha ao menos quatro vértices de grau
.
Resposta
Todo grafo planar simples com
vértices tem pelo menos quatro vértices de grau menor ou igual a 5.