Diferenças

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

--- grafos:teo5cores [2023/06/11 14:40] – edição externa 127.0.0.1
+++ grafos:teo5cores [2023/06/11 14:49] (atual) – edição externa 127.0.0.1
@@ Linha 9: / Linha 9: @@
 //**Demonstração:**//
-Tomemos $G$ um grafo planar com $n \geq 6$ vértices e $m$ arestas.
+Tomemos $G$ um grafo planar com $n \geq 6$ vértices e $m$ arestas. Sabemos que o grafo possui no máximo $3n - 6$ arestas. Assim iremos por indução supor que todo grafo com menos de $n$ vértices possui $5$-coloração.
-  * Sabemos que o grafo possui no máximo $3n - 6$ arestas
-  * Assim iremos por indução supor que todo grafo com menos de n vértices possui 5-coloração
-       *$d(G) = \frac{\sum(d(v))}{n} =\frac{2m}{n} \leq \frac{2(3n - 6)}{n} < 6$
-  * Tomemos $v$ um vértice de $G$ de grau menor ou igual a 5
-       * Se $d(v) < 5$ então este vértice $v$ seria a quinta cor
-       * Se $d(v) = 5$ e todos os vértices adjacentes de $v$ possuem cores distintas
-       * Tome $D$ um disco em torno de $v$, pequeno a ponto de apenas conter linhas retas de segmentos que contém $v$, agora vamos enumerar estes segmentos da forma que aparecem dentro do disco como $s_1,\dots,s_5$ e $v_i$ o vértice contendo $s_i$, como na figura a seguir.
-{{:grafos:5cores.png?700|}}
+$$d(G) = \frac{\sum(d(v))}{n} =\frac{2m}{n} \leq \frac{2(3n - 6)}{n} < 6$$
-  *Vamos mostrar que todo caminho $P$ conectando $v_1 -- v_3$ separa $v_2$ de $v_4$
+Tomemos $v$ um vértice de $G$ de grau menor ou igual a $5$. Se $d(v) < 5$ então este vértice $v$ seria a quinta cor; se $d(v) = 5$, todos os vértices adjacentes de $v$ possuem cores distintas.
-      * Isso ocorre apenas no caso que em o ciclo $C = vv_1Pv_3v$ separa $v_2$ de $v_4$, provamos que isso é verdade mostrando que $v_2$ e $v_4$ estão em faces diferentes
-      * Tome $x_2$ de $s_2$ em $D$ e $x_4$ de $s_4$ em $D$, assim $D \setminus (s_1 \cup s_3) \subset \mathbb{R}^2 \setminus C$ pode ser conectado por um polígono de $x_2$ a $x_4$ , assim pelo Teorema da curva Jordan para polígonos, $x_2$ e $x_4$, estão em faces diferentes do ciclo $C$.
-  * Tomando agora $i,j \in \{1,\dots,5\}$, tome $H_{i,j}$ os subgrafos de $G \setminus v$ induzidos.
-      * Podemos supor que a componente $C_1$ de $H_{1,3}$ contém $v_1$ e $v_3$.
-      * Inclusive se trocarmos as cores de 1 e 3 em todos os vértices de $C_1$, obtemos uma nova 5-coloração de $G \setminus v$.
-           * Se $v_3 \notin C_1$, então $v_1$ e $v_3$ são ambos coloridos com 3 nessa nova coloração, e podemos então pinta $v$ com a cor 1.
-           * Assim $H_{1,3}$ contém uma caminho $P$ de $v_1 -- v_3$, como mostrado antes $P$ separa $v_2$ e $v_4$ em $G \setminus v$.
-           * Já que $P \cap H_{2,4} = \emptyset$, por isso $v_2$ e $v_4$ estão em faces diferentes de $H_{2,4}$.
-           * Na componente contendo $v_2$ , trocamos as cores 2 e 4 e trocamos $v_2$ com a cor 4, assim $v$ não possui vizinhos coloridos com 2, e podemos colorí-lo com essa cor. <wrap right>$\square$</wrap>
+Tome $D$ um disco em torno de $v$, pequeno a ponto de apenas conter linhas retas de segmentos que contém $v$, agora vamos enumerar estes segmentos da forma que aparecem dentro do disco como $s_1,\dots,s_5$ e $v_i$ o vértice contendo $s_i$, como na figura a seguir.
+{{ :grafos:5cores.png?500 |}}
+Vamos mostrar que todo caminho $P$ conectando $v_1 - v_3$ separa $v_2$ de $v_4$. Isso ocorre apenas no caso que em o ciclo $C = vv_1Pv_3v$ separa $v_2$ de $v_4$, provamos que isso é verdade mostrando que $v_2$ e $v_4$ estão em faces diferentes. Tome $x_2$ de $s_2$ em $D$ e $x_4$ de $s_4$ em $D$, assim $D \setminus (s_1 \cup s_3) \subset \mathbb{R}^2 \setminus C$ pode ser conectado por um polígono de $x_2$ a $x_4$ , assim pelo Teorema da curva Jordan para polígonos, $x_2$ e $x_4$, estão em faces diferentes do ciclo $C$.
+Tomando agora $i,j \in \{1,\dots,5\}$, tome $H_{i,j}$ os subgrafos de $G \setminus v$ induzidos. Podemos supor que a componente $C_1$ de $H_{1,3}$ contém $v_1$ e $v_3$. Inclusive, se trocarmos as cores de $1$ e $3$ em todos os vértices de $C_1$, obtemos uma nova $5$-coloração de $G \setminus v$.
+Se $v_3 \notin C_1$, então $v_1$ e $v_3$ são ambos coloridos com $3$ nessa nova coloração, e podemos então pintar $v$ com a cor $1$. Assim $H_{1,3}$ contém uma caminho $P$ de $v_1 - v_3$, como mostrado antes $P$ separa $v_2$ e $v_4$ em $G \setminus v$. Já que $P \cap H_{2,4} = \emptyset$, por isso $v_2$ e $v_4$ estão em faces diferentes de $H_{2,4}$. Na componente contendo $v_2$ , trocamos as cores $2$ e $4$ e trocamos $v_2$ com a cor $4$, assim $v$ não possui vizinhos coloridos com $2$, e podemos colorí-lo com essa cor.
+<wrap right>$\square$</wrap>
 </WRAP>