Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:lema1planar [2023/04/20 13:24] – piva
+++ grafos:lema1planar [2023/04/20 14:10] (atual) – edição externa 127.0.0.1
@@ Linha 38: / Linha 38: @@
 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.
+<wrap right>$\square$</wrap>
 </WRAP>
@@ Linha 50: / Linha 51: @@
 //**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 ([[grafos:graphplanar#lema_1 | Lema 1]]), eles são planares pelo Lema 4.4.3.
+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 ([[grafos:graphplanar#lema_1 | Lema 1]]), eles são planares pelo [[grafos:graphplanar#lema_2 |Lema 2]].
-Para cada J separadamente, escolha um desenho de G, uma face F com a aresta X em seu limite e um vértice Z no limite de F. Seja K um T ou T no grafo abstrato G.
+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$.
-(FIGURAAAAA
+Um $TK^5$ ou $TK_[3,3}$ em $G+z_1z_2$:
+{{ :grafos:graph203.png?400 |}}
+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 [[grafos:eulersform#corolario_2 |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 [[grafos:eulersform#corolario_2 |Corolário 2]].
+<wrap right>$\square$</wrap>
+</WRAP>
+----
+<WRAP round info>
+=== Referências ===
+  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch4.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 105-107. Acesso em 20/04/2023.
-Se todos os vértices de ramificação de K estiverem no mesmo G, então G ou G (ou o próprio G, se Z já for adjacente a X ou Y, respectivamente) contém um T ou T; isso contradiz o Corolário 4.2.11, já que esses grafos são planares pela escolha de Z. Como G não contém quatro caminhos independentes entre G e G , esses subgrafos não podem conter um vértice de ramificação de um T e não podem conter dois vértices de ramificação de um T. Portanto K é um T com apenas um vértice de ramificação V em , digamos, G. Mas também o grafo G, que é planar pela escolha de Z, contém um T. Isso contradiz o Corolário 4.2.11.
 </WRAP>