Vamos chamar de \(\mathcal{C}\) o conjunto das componentes de \(G \setminus F\) e de \(\mathcal{C}^*\) o subconjunto das cpmponentes de \(\mathcal{C}\) vizinhas de \(x\), iremos então definir o seguinte conjunto \(H = G[x \cup \bigcup \mathcal{C}^*]\), agora vamos notar que os elementos de \(\mathcal{C} \setminus \mathcal{C}^* \in G \setminus (F \setminus x)\).

Vamos notar que, \(F`\) encontra apenas finitas componentes de \(\mathcal{C}^*\), pois caso encontrasse infinitamente \(F`\) reduziria \(\mathcal{C}^*\), assim as que não encontram são subgrafos das componentes de \(G \setminus F`\) que contém \(x\).

Assim \(\mathcal{C}^*\) não pode ser ordem determinante, pois caso fosse, \(x\) estaria ligado a infinitos componentes de grau \(\geq \lambda\), então pela proposição 3, considerando \(\circ(G) > \lambda\), neste caso, \(F`\) não poderia ser um redutor, pois existem apenas finitas componentes de tamanho \(\geq \lambda\) e \(\circ(H) = \circ(G)\).

Portanto \(\circ(H) < \circ(G)\) e como \(\circ(C) \leq \circ(H)\), temos que \(\circ(C) < \circ(G)\) para toda componentes \(C \in \mathcal{C} \setminus \mathcal{C}^*\), o que implica que \(F \setminus x\) é redutor.

  • grafos/raylesslema2.txt
  • Última modificação: 2024/04/29 17:05
  • por maugsia