Relação de Euler (prova combinatória)

Nos dois últimos posts, provamos a relação de Euler usando grafos e geometria elementar. Neste post, provaremos usando contagem dupla.

Teorema (da relação de Euler). Se $P$ é um poliedro convexo com $V$ vértices, $E$ arestas e $F$ faces, então vale que $$V-E+F = 2.$$

Demonstração. Primeiro "abra" o poliedro de modo que todas as faces esteja sobre um plano. Fazemos uma contagem dupla da soma S de todo os ângulos internos do poliedro resultante. Sejam $N_1,N_2,\ldots,N_F$ a quantidade de arestas (e de vértices) de cada uma das faces, sendo $N_1$ a da face que delimita todas as outras. Uma vez que a soma dos ângulos interno de um polígono de $n$ lado é $(n-2)\cdot 180º$, temos que

$$S = (N_2-2) 180º + (N_3-2)180º + \cdots + (N_F-2)180º\\=(N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º.$$

Fazendo, agora, a contagem através dos vértices, temos que

$$S = (V-N_1)360º + (N_1-2)180º.$$

Igualando as duas somas, obtemos que

$$(N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º = (V-N_1)360º + (N_1-2)180º,$$

que é equivalente a

$$2V -  (N_1 + N_2 + \cdots + N_F) + 2F = 4$$

Observe que a soma $N_1 + N_2 + \cdots + N_F$ é igual a $2E$, pois cada aresta aparece em exatas duas faces distintas. Portanto, $V-E+F = 2$. Isto conclui a demonstração.