Lema 1

Seja $\mathcal{X}$ um conjunto de grafos $3$-conexos. Seja $G$ um grafo com uma separação própia $\{V_{1}, V_{2}\}$ de ordem $\kappa (G) \leq 2$. Se $G$ é maximal com relação a arestas sem minors topológicos em $\mathcal{X}$, então $G_{1} := G[V_{1}]$ e $G_{2} := G[V_{2}]$ também são e $G_{1} \cap G_{2} = K^{2}$, ou seja, é uma aresta.

Demonstração:

Observe primeiro que todo vértice $v \in S := V_1 \cap V_2$ tem um vizinho em cada componente de $G_{i} - s$, $i=1,2$ : caso contrário, $S \setminus \{v\}$ separaria $G$, contradizendo $|S| = \kappa (G)$. Pela maximalidade de $G$, toda aresta $e$ adicionada a $G$ está em um $TX \subseteq G+e$, com $X \in \mathcal{X}$. Para todas as escolhas de $e$ considerada abaixo, a $3$-conectividade de $X$ implicará que os vértices de ramificação deste $T$X estão todos no mesmo $V_{i}$, digamos em $V_1$. (A posição de $e$ sempre será simétrica em relação a $V_1$ e $V_2$, então essa suposição não acarreta perda de generalidade.) O $TX$ encontra $V_2$ no máximo em um caminho $P$ correspondente a uma aresta de $X$.

Se $S = \emptyset$, obtemos uma contradição imediata escolhendo $e$ com uma extremidade em $V_1$ e a outra em $V_2$. Como $G$ é maximal em relação a ter minor topológico, temos uma copia de um $3$-conexo nesse novo grafo. Mas como só há uma aresta entre $V_{1}$ e $V_{2}$, esse $3$-conexo precisa estar inteiro em apenas um dos dois. Mas então ele já estava no grafo original. Como o grafo original não tinha minor topológico, chegamos em uma contradição. Logo, $S \neq \emptyset$.

Se $S=\{v\}$, ou seja, vamos considerar a intersecção como um único vértice. $v$ é um vértice de corte,pois. Deixe $e$ juntar um vizinho $v_1$ de $v$ em $V_1 \setminus S$ a um vizinho $v_2$ de $v$ em $V_2 \setminus S$ (note que esta aresta não pode existir no grafo original, ou $v$ não seria de corte). Então $P$ contém tanto $v$ quanto a aresta $e=v_1v_2$; substituindo seu segmento $vPv_2v_1$ pela aresta $vv_1$ obtemos um minor topológico $TX$ em $G_1 \subseteq G$ (ou seja, esse minor já existia no grafo original) , uma contradição.

Se $G+e$ contém um $TX$, então $G_1$ ou $G_2$ também tem:

Então $|S| = 2$ , digamos $S = \{x,y\}$, com $x$ e $y$ não adjacentes. Se $xy \not \in G$, deixamos $e := xy$ e, no $TX$ resultante, substituímos $e$ por um $x-y$ caminho através de $G_2$. Isso produz um $TX$ em $G$, uma contradição. Portanto, $xy \in G$, e $G[S] = K^2$ como reivindicado.

Logo, $S$ é uma aresta.

Resta mostrar que $G_1$ e $G_2$ são arestas máximas sem um minor topológico em $\mathcal{X}$, isto é, se adicionarmos aresta em um dos lados, ganhamos um minor topológico contido nesse lado. Primeiro, note que os vértices do grafo original do minor estão todos de um lado (caso contrário, conseguiríamos separar removendo os $2$ vértices da intersecção, mas é $3$-conexo).

Portanto, seja $e'$ uma aresta adicional para $G_1$, digamos. Substituindo $xPy$ pela aresta $xy$ se necessário, obtemos um $TX$ em $G+e'$ (que mostra a aresta maximal de $G_1$, conforme desejado) ou em $G_2$ (que contradiz $G_2 \subseteq G$).

Logo, se $G$ é maximal com relação a arestas sem minors topológicos em $\mathcal{X}$, então $G_{1} = G[V_{1}]$ e $G_{2} = G[V_{2}]$ também são.

$\square$

Lema 2

Se $|G| \geq 4$ e $G$ é maximal com relação a arestas com $TK^5,TK_{3,3} \nsubseteq G$, então $G$ é $3$-conexo.

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 seja $G$ maximal com relação a arestas sem um $TK^5$ ou $TK_{3,3}$. Suponha $\kappa (G) \leq 2$, e escolha $G_1$ e $G_2$ como no Lema $1$ logo acima. Para $\mathcal{X} := \{K^5,K_{3,3}\}$, o lema diz que $G_1 \cap G_2$ é um $K^2$, com vértices $x,y$, digamos, e que $G_1$ e $G_2$ também são maximais com relação a arestas sem um $TK^5$ ou $TK_{3,3}$. Portanto, $G_1$ e $G_2$ são um triângulo ou $3$-conexo pela hipótese de indução . Como eles não podem conter $K^5$ ou $K_{3,3}$ mesmo como um minor ordinário ( Lema 1), eles são planares pelo Lema 2.

Para cada $i=1,2$ separadamente, escolha um desenho de $G_{i}$, uma face $f_{i}$ com a aresta $xy$ em seu limite e um vértice $z_{i} \neq x,y$ no limite de $f_{i}$. Seja $K$ um $TK^5$ ou $TK_{3,3}$ no grafo abstrato $G+z_1z_2$.

Um $TK^5$ ou $TK_[3,3}$ em $G+z_1z_2$:

Se todos os vértices de ramificação de $K$ estiverem no mesmo $G_{i}$, então $G_{i} + xz_{i}$ ou $G_{i} + yz_{i}$ (ou o próprio $G_{i}$, se $z_{i}$ já for adjacente a $x$ ou $y$, respectivamente) contém um $TK^5$ ou $TK_{3,3}$; isso contradiz o Corolário 2, já que esses grafos são planares pela escolha de $z_{i}$. Como $G + z_1z_2$ não contém quatro caminhos independentes entre $(G_1-G_2)$ e $(G_2-G_1)$, esses subgrafos não podem conter um vértice de ramificação de um $TK^5$, e não podem conter dois vértices de ramificação de um $TK_{3,3}$. Portanto $K$ é um $TK_{3,3}$ com apenas um vértice de ramificação $v$ em , digamos, $G_2 - G_1$. Mas também o grafo $G_1 + v + \{vx,vy,vz_1\}$, que é planar pela escolha de $z_1$, contém um $TK_{3,3}$. Isso contradiz o Corolário 2.

$\square$