==== Critérios de planaridade algébrica ==== Uma das características mais notáveis ​​de um grafo plano $G$ são seus **//ciclos faciais//**, os ciclos que delimitam uma face. Se $G$ é $2$-conexo, ele é coberto por seus ciclos faciais, então, de certo modo, eles formam um conjunto 'grande'. De fato, o conjunto de ciclos faciais é grande mesmo no sentido de que eles geram todo o espaço do ciclo: cada ciclo em $G$ é facilmente visto como a soma dos ciclos faciais (veja abaixo). Por outro lado, os ciclos faciais cobrem apenas $G$ 'finamente', já que cada aresta está em no máximo dois deles. Nosso primeiro objetivo é mostrar que a existência de uma família de ciclos tão grande, mas pouco difundida, não é apenas uma característica notável da planaridade, mas está em seu cerne: ela a caracteriza. Seja $G=(V,E)$ um grafo qualquer. Chamamos um subconjunto $\mathcal{F}$ de seu espaço de arestas $\varepsilon (G)$ **esparso** se cada aresta de $G$ estiver em no máximo dois conjuntos de $\mathcal{F}$. Por exemplo, o espaço de corte $\mathcal{B}(G)$ tem uma base esparsa: de acordo com a [[grafos:algebralinbas#proposicao_2 |Proposição]] ele é gerado pelos cortes $E(v)$ formado por todas as arestas em um dado vértice $v$, e uma aresta $xy \in G$ está em $E(v)$ apenas para $v=x$ e para $v=y$. === Teorema (MacLane) === //Um grafo é planar se, e somente se, seu espaço de ciclo tem uma base esparsa.// **//Demonstração://** Sendo a afirmação trivial para grafos de ordem no máximo $2$, consideramos um grafo $G$ de ordem no mínimo $3$. Se $\kappa (G) \leq 1$, então $G$ é a união de dois subgrafos induzidos próprios $G_1,G_2$ com $|G_1 \cap G_2| \leq 1$. Então $\mathcal{C}(G)$ é a soma direta de $\mathcal{C}(G_1)$ e $\mathcal{C}(G_2)$ e, portanto, tem uma base esparsa se, e somente se, $\mathcal{C}(G_1)$ e $\mathcal{C}(G_2)$ o fazem. Além disso, $G$ é planar se, e somente se, ambos $G_1$ e $G_2$ são: isso decorre imediatamente do [[.corolario1planar | Teorema de Kuratowski]], mas também de considerações geométricas fáceis. A firmação para $G$ segue indutivamente daquelas para $G_1$ e $G_2$. Para o restante da prova, assumimos agora que $G4 é $2$-conexo. Primeiro assumimos que $G$ é planar e escolhemos um desenho. Pela [[grafos:topicosplan#proposicao_2 |Proposição]], os limites de face de $G$ são ciclos, portanto são elementos de $\mathcal{C}(G)$. Mostraremos que os limites de face geram todos os ciclos em $G$; então $\mathcal{C}(G)$ tem uma base esparsa pelo [[grafos:topintrod#lema_2 |Lema]]. Seja $C \subseteq G$ qualquer ciclo, e seja $f$ sua face interna. Pelo [[grafos:topintrod#lema_2 |Lema]], toda aresta $e$ com $\dot e \subseteq f$ está exatamente em dois limites de face $G[f']$ com $f' \subseteq f$, e toda aresta de $C$ está exatamente em um desses limites de face. Portanto, a soma em $\mathcal{C}(G)$ de todos esses limites de face é exatamente $C$. Reciprocamente, seja $\{C_1, \dots, C_{k}\}$ uma base esparsa de $\mathcal{C}(G)$. Então, para toda aresta $e \in G$, também $\mathcal{C}(G-e)$ tem uma base esparsa. De fato, se $e$ está em apenas um dos conjuntos $C_{i}$, digamos em $C_1$, então $\{C_2, \dots, C_{k}\}$ é uma base esparsa de $\mathcal{C}(G-e)$; se $e$ está em dois de $C_{i}$, digamos em $C_1$ e $C_2$, então $\{C_1+C_2,C_3, \dots\ C_{k}\}$ é tal base. Observe que as duas bases são de fato subconjuntos de $\mathcal{C}(G-e)$ pela [[grafos:algebralinbas#proposicao_1|Proposição]]. Assim, todo subgrafo de $G$ tem um espaço de ciclo com uma base esparsa. Para nossa prova de que $G$ é planar, basta mostrar que os espaços de ciclo de $K^5$ e $K_{3,3}$ (e, portanto, aqueles de suas subdivisões) não têm uma base esparsa: então $G$ não pode conter um $TK^5$ ou $TK_{3,3}$ e, portanto, é planar por [[.corolario1planar | Teorema de Kuratowski]]. Vamos considerar $K^5$ primeiro. Pelo [[grafos:algebralinbas#teorema_2 |Teorema]], $dim \mathcal{C}(K^5) = 6$; seja $\mathcal{B} = \{C_1, \dots,C_6\}$ uma base esparsa,e coloque $C_0 := C_1 + \dots C_6$. Como $\mathcal{B}$ é linearmente independente , nenhum dos conjuntos $C_0, \dots, C_6$ é vazio , então cada um deles contém pelo menos três arestas (conforme, [[grafos:algebralinbas#teorema_1 |Proposição]]). Além disso, como toda aresta de $C_0$ está em apenas uma de $C_1, \dots, C_6$, o conjunto $\{C_1,\dots, C_6\}$ ainda é esparso. Mas isso implica que $K^5$ deve ter mais arestas do que tem, ou seja, obtemos a contradição de $$ 21= 7*3 \leq |C_0|+ \dots + |C_6| \leq 2||K^5|| =20 $$ Para $K_{3,3}$, o [[grafos:algebralinbas#teorema_2|Teorema]] dá $dim \mathcal{C}(K_{3,3}) = 4$; seja $\mathcal{B} = \{C_1, \dots, C_4\}$ uma base esparsa e coloque $C_0 := C_1 + \dots + C_4$. Como $K_{3,3}$ tem circunferência $4$, cada $C_{i}$ contém pelo menos quatro arestas. Obtemos então a contradição de $$20 = 5*4 \leq |C_0|+ \dots + |C_4| \leq 2||K_{3,3}|| = 18$$ ---- É uma das belezas ocultas da teoria da planaridade que dois resultados tão abstratos e aparentemente não intuitivos sobre a geração de conjuntos em espaços de ciclo como o **Teorema de MacLane**, logo acima, e o [[.theoremtuttegeneral | Teorema de Tutte]] conspiram para produzir um critério de planaridade muito tangível para grafos $3$-conexos: === Teorema (Kelmans) === //Um grafo $3$-conexo é planar se, e somente se, todas as arestas estão no máximo (equivalentemente: exatamente) em dois ciclos induzidos não separados.// **//Demonstração://** $(\Rightarrow)$ Esta afirmação segue da [[grafos:limgrafoscub#proposicao_1|Proposição]] e do [[ grafos:topintrod#lema_2|Lema]] (e da [[grafos:topicosplan#proposicao_2|Proposição]] para a versão 'exatamente dois'). $(\Leftarrow)$ Já esta implicação segue do [[.theoremtuttegeneral | Teorema de Tutte]] e do Teorema de MacLane. ---- Vamos concluir com outra caracterização de planaridade, uma com um sabor muito diferente. Uma //extensão linear// de uma ordenação parcial $\leq$ de um conjunto $P$ é uma ordenação total $\leq '$ em $P$ que inclui $\leq$ como um subconjunto de $P^2$. Assim, para qualquer $p \leq q$ em $P$ ainda temos $p \leq 'q$, e para $p,q \in P$ imcomparáveis temos $p <'q$ ou $p >'q$, além disso. A //dimensão// do conjunto parcialmente ordenado $(P,\leq)$ é o menor número de extensões lineares de $\leq$ em $P$ cuja interseção é exatamente $\leq$ : para qualquer $p,q \in P$ incomparáveis deve haver uma extensão linear $\leq '$ com $p <'q$ e outra extensão linear $\leq ''$ com $p >''q$ nesta coleção. A cada grafo $G=(V,E)$ pode-se associar sua //pose de incidência//, o conjunto parcialmente ordenado $(V \cup E, \leq)$ em que $v < e$ se, e somente se, $v$ é um vértice e $e$ é uma aresta em $v$. (Assim, como uma relação, $<$ é o mesmo que $\in$.) === Teorema (Schnyder) === //Um grafo é planar se, e somente se sua pose de incidência tem dimensão $\leq 3$.// ---- === 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. 107-109. Acesso em 06/06/2023.