Diferenças

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

--- grafos:teo5cores [2023/06/11 14:47] – edição externa 127.0.0.1
+++ grafos:teo5cores [2023/06/11 14:49] (atual) – edição externa 127.0.0.1
@@ Linha 21: / Linha 21: @@
 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$.
+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$.
+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.
-           * 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>