Lema da Infinitude de König
Sejam $V_0, V_1, ...$ uma sequência infinita de conjuntos disjuntos (não vazios) e $G$ um grafo definido sobre a união dos termos dessa sequência. Se todo vértice $v \in V_n$ com $n \geq 1$ possui um vizinho $f(v) \in V_{n-1}$, então $G$ contém um raio $v_0 v_1 ...$ com $v_n \in V_n$ para todo $n \in \mathbb N$.
Demonstração: Seja $\mathcal P$ o conjunto de todos os caminhos finitos da forma $v f(v) f\big(f(v)\big) \ldots$ com extremidade em $V_0$. Como $V_0$ é finito e $\mathcal P$ infinto, podemos afirmar que infinitos caminhos em $\mathcal P$ possuem o mesmo vértice $v_0 \in V_0$ como extremidade. Desses caminhos, infinitos coincidem também em seu penúltimo elemento, $v_1 \in V_1$ — pois temos, novamente, um conjunto finito. Note que podemos repetir esse processo sucessivamente; apesar do número de caminhos ser cada vez menor, continua sendo infinito depois de qualquer número finito de passos. Desse modo, $v_n$ está definido para qualquer $n \in \mathbb N$. Por hipótese, cada um dos $v_n \in V_n$ é vizinho de um $v_{n-1} \in V_{n-1}$. Assim, $v_0 v_1 \ldots$ é, de fato, um raio.