grafos:prova1rayless [WikiMat]

Iremos realizar tal demonstração em duas etapas a primeira para mostrar que em \(A\) não existem grafos com raios e a segunda para mostrar que se um grafo não tem raio ele está em \(A\):

a) Vamos supor que existem grafos com raios em \(A\), dessa forma podemos tomar o grafo com raio \(G\) de menor ordem (\(\circ(G)\)) e \(R\) um dos raios de \(G\)

  * Como \(G\) é infinito, por possuir um raio, \(\circ(G) >0\)
  * Tome \(F\) o redutor de \(G\), portanto existe uma componente conexa \(C\) contendo uma cauda (subraio) de \(R\)
  * Portanto \(\circ(C) < \circ(G)\), dessa forma \(C\) é o grafo de menor ordem contendo um raio, o que é uma contradição com a minimalidade de \(G\)

b)Vamos supor que existe \(G\) sem raio tal que \(G \notin A\), ie, para todo \(F\) finito existe alguma componente conexa \(G_0 \notin A\)

  * Vamos tomar \(v_0\) um vértice qualquer de \(G_0\)
  * Então podemos fabricar \(G_1\) componente de \(G_0 - v_0\) e \(G_1 \notin A\), tome então \(v_1 \in G_1\) vizinho de \(v_0\)
  * Então podemos fabricar \(G_2\) componente de \(G_1 - v_1\) e \(G_2 \notin A\), tome então \(v_2 \in G_2\) vizinho de \(v_1\)
  * Realizando tal processo infinitas vezes iremo criar um caminho infinito \(v_0 - v_1 - \dots\), ou seja, um raio

assim \(G\) tem raio, um absurdo