Fórmula de Euler e algumas consequências
O seguinte resultado clássico de Euler (1752), aqui apresentado em sua forma mais simples para o plano, marca uma das origens comuns da teoria dos grafos e da topologia. O teorema relaciona o número de vértices, arestas e faces em um grafo planar: tomados com os sinais corretos, esses números sempre somam $2$.
A forma geral do teorema de Euler também afirma o mesmo para grafos adequadamente embutidos em outras superfícies: a soma obtida é sempre um número fixo dependendo apenas da superfície, não do grafo, e esse número difere para superfícies distintas (fechadas orientáveis). Portanto, quaisquer duas dessas superfícies podem ser distinguidas por um invariante aritmético simples dos grafos embutidos nelas! (Essa conexão fundamental entre grafos e superfícies está no cerne da prova do famoso Teorema do grafo minor de Robertson-Seymour.)
Vamos provar o teorema de Euler em sua forma mais simples:
Teorema: Fórmula de Euler
Seja $G$ um grafo plano conexo com $n$ vértices, $m$ arestas e $\ell$ faces. Então
$$n - m + \ell =2.$$
Demonstração:
Fixamos $n$ e aplicamos indução em $m$. Para $m \leq (n-1)$, $G$ é uma árvore e $m=n-1$, então a afirmação segue da Proposição 1.
Agora seja $m \geq n$. Então $G$ tem uma aresta $e$ que está em um ciclo; seja $G' := G-e$. Pelo Lema 2 $(ii)$, $e$ está no limite de exatamente duas faces $f_1,f_2$ de $G$, e como os pontos em $\dot e$ são todos equivalentes em $\mathbb{R}^2 \setminus G'$, existe uma face $f_{e}$ de $G'$ contendo $\dot e$. Mostramos que:
$$(*) F(G) \setminus \{f_1,f_2\} = F(G') \setminus \{f_{e}\} ;$$
então $G'$ tem exatamente uma face e uma aresta a menos que $G$, e assim a afirmação segue da hipótese de indução para $G'$.
Para uma prova de $(*)$, seja dado primeiro $f \in F(G) \setminus \{f_1,f_2\}$. Pelo Lema 2 $(i)$ temos $G[f] \subseteq G \setminus \dot e = G'$ , e portanto $f \in F(G')$ pelo Lema 2 $(ii)$. Como claramente $f \neq f_{e}$, isso estabelece a inclusão para frente em $(*)$.
Reciprocamente, considere qualquer face $f' \in F(G') \setminus \{f_{e}\}$. Claramente $f' \neq f_1,f_2$ e $f' \cap \dot e = \emptyset$. Portanto, todos os dois pontos de $f'$ estão em $\mathbb{R}^2 \setminus G$ e são equivalentes lá, então $G$ tem uma face $f$ que continua $f'$. Pelo Lema 1 $(i)$, entretanto, $f$ está dentro de um face $f''$ de $G'$. Portanto, $f' \subseteq f \subseteq f''$ e, portanto, $f' = f = f''$ , já que $f'$ e $f''$ são faces de $G'$.
$\square$
Corolário 1
Um grafo plano com $n \geq 3$ vértices tem no máximo $3n -6$ arestas. Toda triangulação plana com $n$ vértices tem $3n -6$ arestas.
Demonstração:
Pela Proposição basta provar a segunda afirmação. Em uma triangulação plana $G$, todo limite de face contém exatamente três arestas, e cada aresta está no limite de exatamente duas faces, pelo Lema 2. O grafo bipartido em $E(G) \cup F(G)$ com conjunto de arestas $\{ef | e \subseteq G[f]\}$, portanto, tem exatamente $2|E(G)| = 3|F(G)|$ arestas. De acordo com esta identidade podemos substituir $\ell$ por $2m/3$ na fórmula de Euler, e obter $m=3n-6$.
$\square$
A fórmula de Euler pode ser útil para mostrar que certos grafos não podem ocorrer como grafos planos. O grafo $K^5$, por exemplo, possui $10 > 3 \cdot 5 - 6$ arestas, mais do que o permitido pelo Corolário $1$ acima. Da mesma forma, $K_{3,3}$ não pode ser um grafo plano. Pois como $K_{3,3}$ é $2$-conexo, mas não contém triângulo, toda face de um plano $K_{3,3}$ seria limitada por um ciclo de comprimento $\geq 4$ ,pela Proposição 2. Como na prova do Corolário $1$ acima isto implica $2m \geq 4 \ell$, que resulta em $m \leq 2n-4$ quando substituído na fórmula de Euler. Mas $K_{3,3}$ tem $9 > 2 \cdot 6 -4$ arestas.
Claramente, junto com os próprios $K^5$ e $K_{3,3}$, suas subdivisões também não podem ocorrer como grafos planos:
Corolário 2
Um grafo plano não contém nem $K^5$ nem $K_{3,3}$ como minor topológico.
Surpreendentemente, verifica-se que esta propriedade simples dos grafos planos os identifica entre todos os outros grafos: como viremos a mostrar mais a frente, um grafo arbitrário pode ser desenhado no plano se, e somente se, não tiver $K^5$ ou $K_{3,3}$ minor(topológico) .
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 97-98. Acesso em 12/04/2024.