grafos:lema1planar

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:lema1planar [2023/04/20 13:46] – edição externa 127.0.0.1grafos: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. 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>  </WRAP> 
  
Linha 59: Linha 60:
  
 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]]. 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.
 +
 </WRAP> </WRAP>
  • grafos/lema1planar.1682009208.txt.gz
  • Última modificação: 2023/04/20 13:46
  • por 127.0.0.1