Definição

Um grafo plano é um par $(V,E)$ de conjuntos finitos com as seguintes propriedades (os elementos de $V$ são novamente chamados de vértices, os de $E$ arestas):

$(i)$ $V \subseteq \mathbb{R}^2$;

$(ii)$ toda aresta é um arco entre dois vértices;

$(iii)$ diferentes arestas têm diferentes conjuntos de extremidades;

$(iv)$ o interior de uma aresta não contém nenhum vértice e nenhum ponto de qualquer outra aresta.

Lema 1

Seja $G$ um grafo plano , $f \in F(G)$ uma face e $H \subseteq G$ um sugrafo.

$(i)$ $H$ tem uma face $f'$ contendo $f$;

$(ii)$ Se a fronteira de $f$ está em $H$, então $f' = f$.

Demonstração: $(i)$ Claramente, os pontos em $f$ são equivalentes também em $\mathbb{R}^2 \setminus H$; seja $f'$ a classe de equivalência de $\mathbb{R}^2 \setminus H$ que os contém.

$(ii)$ Qualquer arco entre $f$ e $f' \setminus f$ encontra a fronteira $X$ de $f$. Se $f' \setminus f \neq \emptyset$ então existe tal arco dentro de $f'$, cujos pontos em $X$ não estão em $H$. Daí $X \not \subseteq H$.

$\square$

Lema 2

Seja $G$ um grafo plano e $e$ uma aresta de $G$.

$(i)$ Se $X$ é a fronteira de uma face de $G$, então $e \subseteq X$ ou $X \cap \dot e = \emptyset$;

$(ii)$ Se $e$ está em um ciclo $C \subseteq G$, então $e$ está na fronteira de exatamente duas faces de $G$, e estas estão contidas em faces distintas de $C$.

$(iii)$ Se $e$ não pertence a nenhum ciclo, então $e$ está na fronteira de exatamente uma face de $G$.

Demonstração: Provamos todas as três afirmações juntas. Comecemos considerando um ponto $x_0 \in \dot e$. Mostramos que $x_0$ está na fronteira de exatamente duas faces ou exatamente de uma, conforme $e$ esteja ou não em um ciclo em $G$. Mostramos então que todos os outros pontos em $\dot e$ estão na fronteira exatamente das mesmas faces que $x_0$. Então as extremidades de $e$ também estarão na fronteira dessas faces, simplesmente porque cada vizinhança de uma extremidade de $e$ é também a vizinhança de um ponto interno de $e$.

Como $G \setminus \dot e$ é compacto, podemos encontrar em torno de cada ponto $x \in \dot e$ um disco aberto $D_{x}$ que encontra $G$ apenas naqueles (um ou dois) segmentos de reta que contêm $x$.

Vamos pegar um ponto interno $x_0$ de um segmento de reta $S \subseteq e$. Então $D_{x_0} \cap G = D_{x_0} \cap S$, logo $D_{x_0} \setminus G$ é a união de dois semi-discos abertos. Como esses meios-discos não encontram $G$, cada um deles está em uma face de $G$. Vamos denotar essas faces por $f_1$ e $f_2$; são as únicas faces de $G$ com $x_0$ em sua fronteira e podem coincidir.

Se $e$ pertence a um ciclo $C \subseteq G$, então $D_{x_0}$ encontra ambas as faces de $C$, pelo Teorema da curva de Jordan para polígonos. Como $f_1$ e $f_2$ estão contidos nas faces de $C$ pelo Lema $1$ acima, isso implica $f_1 \neq f_2$. Se $e$ não pertence a nenhum ciclo, então $e$ é uma ponte e, portanto, liga dois conjuntos de pontos disjuntos $X_1, X_2$ como no Lema da seção anterior, com $X_1 \cup X_2 = G \setminus \dot e$. Claramente, $f_1 \cup \dot e \cup f_2$ é o subconjunto de uma face $f$ de $G-e$. Pelo mesmo Lema , $f \setminus \dot e$ é uma face de $G$, enquanto $f_1, f_2 \subseteq f \setminus \dot e$ por definição de $f$. Como $f_1$ e $f_2$ também são faces de $G$, isso implica $f_1 = f \setminus \dot e = f_2$.

Agora considere qualquer outro ponto $x_1 \in \dot e$. Seja $P$ um arco de $x_0$ a $x_1$ contido em $e$. Como $P$ é compacto, muitos dos discos $D_{x}$ com $x \in P$ cobrem $P$. Vamos enumerar esses discos como $D_0, \dots , D_{n}$ na ordem natural de seus centros ao longo de $P$; adicionando $D_{x_0}$ ou $D_{x_1}$ conforme necessário, podemos assumir que $D_0 = D_{x_0}$ e $D_{n} = D_{x_1}$. Por indução em $n$, prova-se facilmente que todo ponto $y \in D_{n} \setminus e$ pode ser ligado por um arco dentro de $(D_0 \cup \dots \cup D_{n}) \setminus e$ a um ponto $z \in D_0 \setminus e$:

Então $y$ e $z$ são equivalentes em $\mathbb{R}^2 \setminus G$. Portanto, todo ponto de $D_{n} \setminus e$ está em $f_1$ ou em $f_2$, então $x_1$ não pode estar na fronteira de qualquer outra face de $G$. Uma vez que ambos os meios discos de $D_0 \setminus e$ podem ser ligados a $D_{n} \setminus e$ neste caminho (trocar os papéis de $D_0$ e $D_{n}$), descobrimos que $x_1$ está na fronteira de $f_1$ e $f_2$.

$\square$