Proposição 1

Os limites da face em um grafo plano de $3$-conexo são precisamente seus ciclos induzidos não separados.

Demonstração: Seja $G$ um grafo plano $3$-conexo , e seja $C \subseteq G$. Se $C$ é um ciclo induzido não separado, então pelo Teorema da curva de Jordan suas duas faces não podem conter pontos de $G \setminus C$. Portanto, ele limita uma face de $G$.

Reciprocamente, suponha que $C$ limita uma face $f$. Pela proposição, $C$ é um ciclo. Se $C$ tem uma corda $e=xy$, então os componentes de $C- \{x,y\}$ são ligados por um $C$-caminho em $G$, porque $G$ é $3$-conexo. Este caminho e $e$ passam pela outra face de $C$ (não $f$), mas não se cruzam, uma contradição com o Lema 1 $(ii)$.

Resta mostrar que $C$ não separa quaisquer dois vértices $x,y \in G-C$. Pelo Teorema de Menger, $x$ e $y$ estão ligados em $G$ por três caminhos independentes. Claramente, $f$ está dentro de uma face de sua união, e, pelo Lema 1 $(i)$, esta face é limitada por apenas dois dos caminhos. O terceiro, portanto, evita $f$ e seu limite $C$.

$\square$

Proposição 2

Um grafo plano de ordem pelo menos $3$ é maximamente plano se, e somente se, é uma triangulação plana.

Demonstração:

Seja $G$ um grafo plano de ordem pelo menos $3$. É fácil ver que, se toda face de $G$ é limitada por um triângulo, então $G$ é maximamente plano. De fato, qualquer aresta adicional $e$ teria seu interior dentro de uma face de $G$ e suas extremidades no limite dessa face. Portanto, essas extremidades já são adjacentes em $G$, então $G \cup e$ não pode satisfazer a condição $(ii)$ na definição de um grafo plano.

Reciprocamente, assuma que $G$ é maximamente plano e seja $f \in F(G)$ uma face; vamos escrever $H := G[f]$. Como $G$ é maximal como um grafo plano, $G[H]$ é completo: quaisquer dois vértices de $H$ que ainda não sejam adjacentes em $G$ podem ser ligados por um arco através de $f$, estendendo $G$ a um grafo plano maior. Assim, $G[h] = K^{n}$ para algum $n$ ,mas ainda não sabemos quais arestas de $G[H]$ estão em $H$.

Vamos mostrar primeiro que $H$ contém um ciclo. Se não, então $G \setminus H \neq \emptyset$: por $G \supseteq K_{n}$ se $n \geq 3$ , ou então por $|G| \geq 3$. Por outro lado, temos $f \cup H = \mathbb{R}^2$ pela Proposição e, portanto, $G=H$, uma contradição.

Uma vez que $H$ contém um ciclo, basta mostrar que $n \leq 3$: então $H = K^3$ como reivindicado. Suponha $n \geq 4$ e seja $C = v_1v_2v_3v_4v_1$ um ciclo em $G[H] (=K^{n})$ . Por $C \subseteq G$, nossa face $f$ está contida em uma face $f_{C}$ de $C$; seja $f'_{C}$ a outra face de $C$. Como os vértices $v_1$ e $v_3$ estão no limite de $f$, eles podem ser ligados por um arco cujo interior está em $f_{C}$ e evita $G$. Portanto, pelo Lema 1 $(ii)$, a aresta plana $v_2v_4$ de $G[H]$ passa por $f'_{C}$ em vez de $f_{C}$.

Analogamente, já que $v_2, v_4 \in G[f]$, a aresta $v_1v_3$ passa por $f'_{C}$. Mas as arestas $v_1v_3$ e $v_2v_4$ são disjuntas, então isso contradiz o Lema 1 $(ii)$.

$\square$