Relação de Euler (prova com grafos).

Num post anterior, Sólidos Platônicos, usamos a famosa relação de Euler para poliedros, que é dada por:

$$ V - E + F = 2, $$

onde $V$ é o número de vértices de um poliedro convexo, $E$ é o número de arestas e $F$ é o número de faces.

A relação de Euler para poliedros é equivalente a relação de Euler para grafos planares conexos. Afinal, existe uma maneira natural de levar uma instância do primeiro problema para uma instância do segundo: sobre uma face do poliedro, "abra" o poliedro de modo que todas as faces esteja sobre um plano.  Iremos prová-la para grafos planares conexos.

Dado um grafo planar, isto é, um grafo desenhado sobre o plano e sem interseções entre arestas, chamamos de faces internas aquelas regiões internas limitadas pelas arestas do grafo que formam um ciclo. A face externa é a (única) região ilimitada. No que segue, consideramos como face tanto a interna quanto a externa.

Teorema (da relação de Euler). Se $G$ é um grafo planar conexo com $n$ vértices, $m$ arestas e $f$ faces, então vale que $$n - m + f = 2.$$

Demonstração. Provemos por indução em $f$. Se $f=1$, então $G$ é uma árvore e temos que $m = n-1$. Daí, a relação é verificada neste caso.

Suponha que $f >1$ e que para todo grafo conexo com $f-1$ faces a relação seja verdadeira. Como $G$ contém pelo menos duas faces, $G$ não é uma árvore, logo $G$ contém um ciclo. Remova uma aresta deste ciclo. O grafo resultante ainda será conexo e terá o mesmo número de vértices, mas tanto o número de arestas quanto o número de faces diminuirá em uma unidade. Logo, podemos aplicar a hipótese de indução, de modo que temos

$$ n - (m-1) - (f-1) = 2.$$

Portanto, a relação de Euler vale para o grafo original também. Isto completa a prova.

$\square$