grafos:provaprop2rayless [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

Vamos realizar tal demonstração por indução em \(\circ(G) = \lambda\):

Caso 0:

  *\(G \in A(0)\), portanto \(G\) é finito, assim todo \(H \subset G\) é finito e \(\circ(H) = \circ(G)=0\)

HI :

  * \(G \in A(\lambda)\) e \(H \subset G\), então \(H \in A(\mu)\) com \(\mu \leq \lambda\) e \(\circ(H) \leq \circ(G)\)

\(\lambda^+\):

  *\(G \in A(\lambda^+)\), portanto existe \(F\) tal que para toda componente \(C_i \in G \setminus F\) temos que \(C_i \in A(\mu)\) para \(\mu < \lambda^+\), \(F\) é redutor de \(G\)
  *Vamos analisar então \(F \cap H\) com \(H \subset F\), perceba que ele será o conjunto de redução de \(H\), como ilustrado na figura abaixo

{{ :grafos:compconex.jpeg?300 |}}
  *Vamos então chamar as componentes conexas de \(H \setminus H\cap F\) de \(C_i^H\) e trivialmente \(C_i^H \subset C_i\), portanto por hipótese de indução \(C_i^H \in A(\mu)\), pois \(C_i \in A(\mu)\) e \(\circ (C_i^H) \leq \circ(C_i)\) para \(\mu < \lambda^+\) e para todo \(i\)
  *Portanto existe \(F´ = F\cap H\)tal que \(F´\) é redutor de \(H\), assim \(H \in A\) e \(\circ(H) \leq \circ(G)\)