grafos:estruct3connect

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:estruct3connect [2023/05/07 16:17] – pivagrafos:estruct3connect [2023/05/07 17:03] (atual) – edição externa 127.0.0.1
Linha 24: Linha 24:
 Pensando em $G$ como obtido de $G \dot -e$ adicionando $e$, chamemos os vértices de $G \dot -e$ de vértices //antigos// de $G$, e qualquer outro vértice de $G$ (que será um fim de $e$) de novo vértice //novo//. Lembrando que $G \dot -e$, sendo $3$-conexo, não possui arestas paralelas, é fácil ver que, em $G$, não há dois vértices $x_1,x_2$ que possam separar um novo vértice de todos os vértices antigos. Portanto, basta mostrar que $\{x_1,x_2\}$ não pode separar dois vértices antigos. Se o fizessem, esses vértices antigos seriam separados em $G \dot -e$  por $x_1'$ e $x_2'$, onde $x_{i}' = x_{i}$  ou, se $x_{i}$ for novo, $x_{i}'$ é a aresta de $G \dot -e$ subdividida por $x_{i}$. Pelo [[.cicloDeltaKConexidade| Teorema]], isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo. Pensando em $G$ como obtido de $G \dot -e$ adicionando $e$, chamemos os vértices de $G \dot -e$ de vértices //antigos// de $G$, e qualquer outro vértice de $G$ (que será um fim de $e$) de novo vértice //novo//. Lembrando que $G \dot -e$, sendo $3$-conexo, não possui arestas paralelas, é fácil ver que, em $G$, não há dois vértices $x_1,x_2$ que possam separar um novo vértice de todos os vértices antigos. Portanto, basta mostrar que $\{x_1,x_2\}$ não pode separar dois vértices antigos. Se o fizessem, esses vértices antigos seriam separados em $G \dot -e$  por $x_1'$ e $x_2'$, onde $x_{i}' = x_{i}$  ou, se $x_{i}$ for novo, $x_{i}'$ é a aresta de $G \dot -e$ subdividida por $x_{i}$. Pelo [[.cicloDeltaKConexidade| Teorema]], isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 45: Linha 46:
  
 Portanto $P$ satisfaz $(*)$. Suprimindo quaisquer vértices de grau $2$ em $H \cup P$ obtemos um multigrafo $J'$ tal que $J' \dot -e =J$, onde $e$ é a aresta correspondente a $P$. Por $(*)$ a aresta $e$ não é paralela a uma aresta de $J$, então $J'$ é de fato um grafo. Pelo Lema $1$ acima, $J'$ é $3$-conexo. Logo, $J' \backsimeq G$ pela maximalidade de $J$, completando a prova. Portanto $P$ satisfaz $(*)$. Suprimindo quaisquer vértices de grau $2$ em $H \cup P$ obtemos um multigrafo $J'$ tal que $J' \dot -e =J$, onde $e$ é a aresta correspondente a $P$. Por $(*)$ a aresta $e$ não é paralela a uma aresta de $J$, então $J'$ é de fato um grafo. Pelo Lema $1$ acima, $J'$ é $3$-conexo. Logo, $J' \backsimeq G$ pela maximalidade de $J$, completando a prova.
 +
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
Linha 66: Linha 69:
 Se $G$ é $3$-conexo, use o Lema $2$ acima para encontrar $G_{n} \dots , G_0$ sucessivamente. Reciprocamente, se $G_0 \dots G_{n}$ é qualquer sequência de grafos satisfazendo $(i)$ e $(ii)$, então todos esses grafos, e em particular $G = G_{n}$, são $3$-conexos pelo Lema $1$ acima. Se $G$ é $3$-conexo, use o Lema $2$ acima para encontrar $G_{n} \dots , G_0$ sucessivamente. Reciprocamente, se $G_0 \dots G_{n}$ é qualquer sequência de grafos satisfazendo $(i)$ e $(ii)$, então todos esses grafos, e em particular $G = G_{n}$, são $3$-conexos pelo Lema $1$ acima.
  
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  
  • grafos/estruct3connect.1683487053.txt.gz
  • Última modificação: 2023/05/07 16:17
  • por piva