Proposição

$(i)$ Todo grafo plano maximal é maximamente planar.

$(ii)$ Um grafo planar com $n \geq 3$ vértices é maximamente planar se, e somente se, tiver $3n-6$ arestas.

Demonstração: O resultado segue da aplicação da Proposição 2 e do Corolário 1.

$\square$

Lema 1

Um grafo contém $K^5$ ou $K_{3,3}$ como minor se, e somente se, contém $K^5$ ou $K_{3,3}$ como minor topológico.

Demonstração:

Pelo já exposto anteriormente, basta mostrar que todo grafo $G$ com um $K^5$ minor contém $K^5$ como minor topológico ou $K_{3,3}$ como minor. Então suponha que $G \succeq K^5$, e seja $K$ um modelo mínimo de $K^5$ em $G$. Então todo conjunto de ramificação de $K$ induz uma árvore em $K$, e entre quaisquer dois conjuntos de ramificação $K$ tem exatamente uma aresta. Se tomarmos a árvore induzida por um conjunto de ramificação $V_{x}$ e adicionarmos a ela as quatro arestas que a unem a outros conjuntos de ramificação, obtemos outra árvore, digamos $T_{x}$. Pela minimalidade de $K$, a árvore $T_{x}$ tem exatamente $4$ folhas, os $4$ vizinhos de $V_{x}$ em outros conjuntos de ramos.

Todo $IK^5$ contém um $TK^5$ ou $IK_{3,3}$:

Se cada uma das cinco árvores $T_{x}$ é um $TK_{1,4}$, então $K$ é um $TK^5$ e terminamos. Se uma das árvores $T_{x}$ não é um $TK_{1,4}$, então ele tem exatamente dois vértices de grau $3$. Contraindo $V_{x}$ sobre esses dois vértices e todos os outros ramos definidos para um único vértice, obtemos um gráfico em $6$ vértices contendo um $K_{3,3}$. Assim, $G \succeq K_{3,3}$ como desejado.

$\square$

Lema 2

Todo grafo $3$-conexo $G$ sem um $K^5$ ou $K_{3,3}$ minor é planar.

Demonstração:

Aplicamos indução em $|G|$. Para $|G| = 4$ temos $G=K^4$, e a afirmação é válida. Agora seja $|G| > 4$, e assuma que a afirmação é verdadeira para grafos menores. Pelo Lema $3.2.4$, $G$ tem uma aresta $xy$ tal que $G \setminus xy$ é novamente $3$-conexo. Como a 'relação minor' é transitiva, $G \setminus xy$ também não tem $K^5$ ou $K_{3,3}$ minor. Assim, por hipótese de indução, $G \setminus xy$ tem um desenho $\tilde {G}$ no plano. Seja $f$ a face de $\tilde{G} - xy$ contendo o ponto $v_{xy}$, e seja $C$ a fronteira de $f$. Seja $X := N_{G}(x) \setminus \{y\}$ e $Y := N_{G}(y) \setminus \{x\}$ ; então $X \cup Y \subseteq V(C)$, porque $v_{xy} \in f$. Claramente,

$$\tilde{G'} := \tilde{G} - \{v_{xy}v \mid v \in Y \setminus X\}$$

pode ser visto como um desenho de $G-y$, no qual o vértice $x$ é representado pelo ponto $v_{xy}$. Nosso objetivo é adicionar $y$ a esse desenho para obter um desenho de $G$.

$\tilde{G}$ como um desneho de $G-v_{xy}$: o vértice $x$ é representado pelo ponto $v_{xy}$:

Como $\tilde{G}$ é $3$-conexo, $\tilde{G} - v_{xy}$ é $2$-conexo, então, pela Proposição 2 $C$ é um ciclo. Seja $x_1, \dots , x_{k}$ uma enumeração ao longo deste ciclo dos vértices em $X$ e seja $P_{i} = x_{i} \dots x_{i+1}$ os $X$-caminhos em $C$ entre eles $(i=1, \dots ,k$ ; com $x_{k+1} := x_1)$. Vamos mostrar que $Y \subseteq V(P_{i})$ para algum $i$. Suponha que não. Se $y$ tem um vizinho $y' \in \dot P_{i}$ para algum $i$ , tem outro vizinho $y'' \in C-P_{i}$, e estes são separados em $C$ por $x' := x_{i}$ e $x'' := x_{i+1}$. Se $Y \subseteq X$ e $|Y \cap X| \leq 2$, então $y$ tem exatamente dois vizinhos $y',y''$ em $C$, mas não no mesmo $P_{i}$, então novamente $y'$ e $y''$ são separados em $C$ por dois vértices $x',x'' \in X$. Em ambos os casos, $x,y',y''$ e $y,x',x''$ são os vértices ramificados de $TK_{3,3}$ em $G$ , uma contradição. O único caso restante é que $y$e $x$ têm três vizinhos comuns em $C$. Então eles formam um $TK^5$ com $x$ e $y$, novamente uma contradição.

Fixe $i$ de forma que $Y \subseteq P_{i}$. O conjunto $C \setminus P_{i}$ está contido em uma das duas faces do ciclo $C_{i} := xx_{i}P_{i}x_{i+1}x$; denotamos a outra face de $C_{i}$ por $f_{i}$. Como $f_{i}$ contém pontos de $f$ (perto de $x$), mas nenhum ponto de seu limite $C$, temos $f_{i} \subseteq f$. Além disso, as arestas planas $xx_{j}$ com $j \not \in \{i,i+1\}$ encontram $C_{i}$ somente em $x$ e terminam fora de $f_{i}$ em $C \setminus P_{i}$, então $f_{i}$ não encontra nenhuma dessas arestas. Portanto, $f_{i} \subseteq \mathbb{R}^2 \setminus \tilde{G'}$, isto é, $f_{i}$ está contido em (e, portanto, igual a) uma face de $\tilde{G'}$. Podemos, portanto, estender $\tilde{G'}$ a um desenho de $G$ colocando $y$ e suas arestas incidentes em $f_{i}$.

$\square$