Proposição: Todo grafo conexo infinito possui um vértice de grau infinito ou contém um raio.

Demonstração: Suponhamos $G=(V,E)$ grafo conexo infinito localmente finito. Note que basta mostrar que $G$ contém um raio.

De fato, fixemos $v\in V(G)$ e definamos então $V_n$ o conjunto de vértices a uma distância $n$ de $v$.

Por ser localmente finito, temos que cada $V_n$ é finito, além disso, por $G$ ser infinito e conexo, $V_n\ne\varnothing$ $\forall n\in\mathbb{N}$.

Sendo assim, dado um vértice $w$ em $V_{n+1}$, temos que existe um vértice vizinho $w'$ de $w$ em $V_n$, pois $w$ está a uma distância de $n+1$ de $v$, se e somente se existe um caminho $v-w$ de $n+1$ vértices e, portanto, o caminho $v-w'$ (caminho $v-w$ sem o $w$) é um caminho de $n$ elementos onde $w'\in V_n\cap N(w)$.

Por fim, pelo Lema da Infinitude de König, $G$ contém um raio. $\blacksquare$

Lema da Estrela-pente: Seja $G=(V,E)$ um grafo conexo infinito e $U \subseteq V(G)$ infinito. Então $G$ contém um pente com todos os dentes em $U$ ou uma subdivisão de uma estrela com todas as suas folhas em $U$.

Demonstração: Como $G$ é conexo, temos que para quaisquer dois vértices de $U$ existe um caminho entre eles. Temos que este caminho é uma árvore a qual cada aresta está em um caminho entre dois vértices de $U$. Podemos “aumentar” sucessivamente esta árvore com novos caminhos entre elementos de $U$ de modo que este caminho com o anterior ainda seja uma árvore. Pelo Lema de Zorn, existe uma árvore maximal $T$ que satisfaz estas condições. Já que $U$ é infinito e $G$ é conexo, $T$ há de ser infinito também, já que é maximal.

Deste modo, se $T$ possui um vértice de grau infinito então $G$ contém a subdivisão da estrela.

Caso $T$ seja localmente finito, então, pela proposição anterior, $T$ possui um raio $R$. Podemos construir uma sequência de caminhos de $R$ a $U$ disjuntos $(P_n)_{n\in\mathbb{N}}$ em $T$. Dado $n\in\mathbb{N}$, escolhemos $v\in R$ de forma que $vR$ (raio a partir do vértice $v$) não toca nenhum dos $P_i$'s $\forall i<n$. Temos que a primeira aresta de $vR$ está em um caminho $P$ entre dois vértices de $U$ (pela construção de $T$). Tomemos $P$ minimal e “saindo” na mesma direção de $R$, isto é, o primeiro vértice de $vP$ é $v$. Então $vP$ é da forma $vPwR$, onde $wP$ é um caminho de $R$ a $U$. Definimos $P_n:=wP$ e temos que $P_n\cap P_i=\varnothing$. Estes caminhos de $R$ a $U$ são as hastes do pente que queríamos ou então um caminho contido em $R$. $\blacksquare$