grafos
O matemático suiço do século XVIII, Leonhard Euler percebeu que um grafo simples, planar (desenhado na sua forma planar) e conexo divide o plano em um certo número de regiões, incluindo regiões totalmente fechadas e a região infinita exterior. Euler estabeleceu uma relação entre o número de arestas, o número de vértices e o número de regiões para tais gráficos que é dada pela fórmula:
n – a + r = 2
onde n é o número de vértices, a é o número de arestas e r é o número de regiões.
Verificação da fórmula de Euler
Considere os tres grafos que se seguem:
1 2 3
Vamos demonstrar a fórmula de Euler por indução.
No grafo 1 o número de arestas é a = 0, consistindo o grafo de um único vértice. Portanto:
n = 1 a = 0 r = 1
De modo que a fórmula n - a + r = 2 se verifica.
Assumimos agora que a fórmula se verifica para qualquer grafo conexo, planar e simples, com k arestas, e consideremos o grafo com k+1 arestas. Para dedução indutiva devemos relacionar o caso de “k+1” com o caso de “k” arestas. Vamos considerar então dois casos de “k+1” arestas.
Caso 1: O grafo tem um vértice de grau 1 como na figura 2. Eliminamos então a aresta e vértice, que conecta o vertice de grau 1. Isto nos deixa com um grafo de k arestas, algum número n vértices e algum número de regiões, r para os quais n - a + r = 2
No grafo original, antes de retirar a aresta e o nó deve também valer a fórmula, ou seja
(n + 1) – (a+1) + r = 2
que pela hipótese de indução é verdadeira.
Caso 2: O grafo não vértices de grau 1, como é o caso da figura 3 acima. Retiramos então uma aresta que define uma região fechada. O resultado é um grafo planar simples com k arestas, algum número n de vértices, da forma:
n – k + r =3 – 2 + 1 =2
verificando-se a