grafos:estruct3connected

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:estruct3connected [2023/05/07 16:27] – pivagrafos:estruct3connected [2023/05/07 17:04] (atual) – edição externa 127.0.0.1
Linha 21: Linha 21:
 Como $x$ e $y$ são adjacentes, $G-\{z,v,w\}$ tem um componente $D$ tal que $D \cap \{x,y\} = \emptyset$. Então todo vizinho de $v$ em $D$ está em $C$ (desde que $v \in C$), então $D \cap C = \emptyset$ e, portanto, $D \subsetneq C$ pela escolha de $D$. Isso contradiz a escolha de $xy,z$ e $C$. Como $x$ e $y$ são adjacentes, $G-\{z,v,w\}$ tem um componente $D$ tal que $D \cap \{x,y\} = \emptyset$. Então todo vizinho de $v$ em $D$ está em $C$ (desde que $v \in C$), então $D \cap C = \emptyset$ e, portanto, $D \subsetneq C$ pela escolha de $D$. Isso contradiz a escolha de $xy,z$ e $C$.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 46: Linha 47:
 Então $C_2$ não contém ambos os vértices $x,y$ nem um vértice $v \notin \{x,y\}$: caso contrário, $v_{xy}$ ou $v$ estariam separados de $C_1$ em $G_{i}$ por no máximo dois vértices, uma contradição. Mas agora $C_2$ contém apenas um vértice: $x$ ou $y$. Isso contradiz nossa suposição de que $d(x),d(y) \geq 3$. Então $C_2$ não contém ambos os vértices $x,y$ nem um vértice $v \notin \{x,y\}$: caso contrário, $v_{xy}$ ou $v$ estariam separados de $C_1$ em $G_{i}$ por no máximo dois vértices, uma contradição. Mas agora $C_2$ contém apenas um vértice: $x$ ou $y$. Isso contradiz nossa suposição de que $d(x),d(y) \geq 3$.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
  • grafos/estruct3connected.1683487645.txt.gz
  • Última modificação: 2023/05/07 16:27
  • por piva