Essa é uma revisão anterior do documento!
Alguns resultados sobre grafos planares
Corolário
A fronteira de uma face é sempre o conjunto de pontos de um subgrafo.
O subgrafo de $G$ cujo conjunto de pontos é a fronteira de uma face $f$ diz-se que limita $f$ e é chamado de limite; nós o denotamos por $G[f]$. Diz-se que uma face é incidente com os vértices e arestas de seu limite. Pelo Lema 1 $(ii)$, toda face de $G$ é também uma face de seu limite; usaremos esse fato frequentemente nas provas que virão.
Proposição 1
Uma floresta plana tem exatamente uma face.
Demonstração: A prova desta proposição é obtida usando indução no número de arestas e o Lema 2.
$\square$
Com apenas uma exceção, faces diferentes de um grafo plano têm limites diferentes:
Lema
Se um grafo plano tiver faces diferentes com o mesmo limite, então o grafo é um ciclo.
Demonstração: Seja $G$ um grafo plano , e seja $H \subseteq G$ o limite de faces distintas $f_1,f_2$ de $G$. Como $f_1$ e $f_2$ também são faces de $H$, a Proposição 1 acima implica que $H$ contém um ciclo $C$. Pelo Lema 2 $(ii)$ , $f_1$ e $f_2$ estão contidos em diferentes faces de $C$. Visto que $f_1$ e $f_2$ têm todo o $H$ como limite,isso implica que $H = C$: qualquer outro vértice ou aresta de $H$ estaria em uma das faces de $C$ e, portanto, não no limite da outra. Assim, $f_1$ e $f_2$ são faces distintas de $C$. Como $C$ tem apenas duas faces, segue-se que $f_1 \cup C \cup f_2 = \mathbb{R}^2$ e, portanto, $G=C$.
$\square$
Proposição 2
Em um grafo plano $2$-conexo, cada face é limitada por um ciclo.
Demonstração: Seja F uma face em um grafo plano 2-conexo G. Mostramos por indução em ||G|| que G[f] é um ciclo. Se G é ele próprio um ciclo, isto é válido pelo Teorema 4.1.1; portanto, assumimos que G não é um ciclo.
Pela Proposição 3.1.1, existe um grafo plano 2-conexo H e um plano H-caminho P tal que G. O interior de P está em uma face F de H, que pela hipótese de indução é limitada por um ciclo C.
Se G, então F também é uma face de H(Lema 4.2.1(ii)), e estamos em casa pela hipótese de indução. Se G, então H encontra P, então H e J. Pelo Lema 4.2.1(ii), então , F é uma face de P e portanto limitada por um ciclo(Lema 4.1.2(i)).
$\square$