| Próxima revisão | Revisão anterior |
| grafos:eulersform [2023/04/12 20:18] – criada piva | grafos:eulersform [2023/04/20 14:05] (atual) – edição externa 127.0.0.1 |
|---|
| Reciprocamente, considere qualquer face $f' \in F(G') \setminus \{f_{e}\}$. Claramente $f' \neq f_1,f_2$ e $f' \cap \dot e = \emptyset$. Portanto, todos os dois pontos de $f'$ estão em $\mathbb{R}^2 \setminus G$ e são equivalentes lá, então $G$ tem uma face $f$ que continua $f'$. Pelo [[grafos:topintrod#lema_1 | Lema 1 $(i)$]], entretanto, $f$ está dentro de um face $f''$ de $G'$. Portanto, $f' \subseteq f \subseteq f''$ e, portanto, $f' = f = f''$ , já que $f'$ e $f''$ são faces de $G'$. | Reciprocamente, considere qualquer face $f' \in F(G') \setminus \{f_{e}\}$. Claramente $f' \neq f_1,f_2$ e $f' \cap \dot e = \emptyset$. Portanto, todos os dois pontos de $f'$ estão em $\mathbb{R}^2 \setminus G$ e são equivalentes lá, então $G$ tem uma face $f$ que continua $f'$. Pelo [[grafos:topintrod#lema_1 | Lema 1 $(i)$]], entretanto, $f$ está dentro de um face $f''$ de $G'$. Portanto, $f' \subseteq f \subseteq f''$ e, portanto, $f' = f = f''$ , já que $f'$ e $f''$ são faces de $G'$. |
| |
| | <wrap right>$\square$</wrap> |
| </WRAP> | </WRAP> |
| |
| Pela [[grafos:limgrafoscub#proposicao_2 | Proposição]] basta provar a segunda afirmação. Em uma triangulação plana $G$, todo limite de face contém exatamente três arestas, e cada aresta está no limite de exatamente duas faces, pelo [[grafos:topintrod#lema_2 |Lema 2]]. O grafo bipartido em $E(G) \cup F(G)$ com conjunto de arestas $\{ef | e \subseteq G[f]\}$, portanto, tem exatamente $2|E(G)| = 3|F(G)|$ arestas. De acordo com esta identidade podemos substituir $\ell$ por $2m/3$ na fórmula de Euler, e obter $m=3n-6$. | Pela [[grafos:limgrafoscub#proposicao_2 | Proposição]] basta provar a segunda afirmação. Em uma triangulação plana $G$, todo limite de face contém exatamente três arestas, e cada aresta está no limite de exatamente duas faces, pelo [[grafos:topintrod#lema_2 |Lema 2]]. O grafo bipartido em $E(G) \cup F(G)$ com conjunto de arestas $\{ef | e \subseteq G[f]\}$, portanto, tem exatamente $2|E(G)| = 3|F(G)|$ arestas. De acordo com esta identidade podemos substituir $\ell$ por $2m/3$ na fórmula de Euler, e obter $m=3n-6$. |
| |
| | <wrap right>$\square$</wrap> |
| </WRAP> | </WRAP> |
| |
| |
| <WRAP round box 100%> | <WRAP round box 100%> |
| === Corlário === | === Corolário 2 === |
| //Um grafo plano não contém nem $K^5$ nem $K_{3,3}$ como minor topológico.// | //Um grafo plano não contém nem $K^5$ nem $K_{3,3}$ como minor topológico.// |
| </WRAP> | </WRAP> |
| |
| Surpreendentemente, verifica-se que esta propriedade simples dos grafos planos os identifica entre todos os outros grafos: como viremos a mostrar mais a frente, um grafo arbitrário pode ser desenhado no plano se, e somente se, não tiver $K^5$ ou $K_{3,3}$ minor(topológico) . | Surpreendentemente, verifica-se que esta propriedade simples dos grafos planos os identifica entre todos os outros grafos: como viremos a mostrar mais a frente, um grafo arbitrário pode ser desenhado no plano se, e somente se, não tiver $K^5$ ou $K_{3,3}$ minor(topológico) . |
| | |
| | ---- |
| | |
| | <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. 97-98. Acesso em 12/04/2024. |
| | |
| | </WRAP> |