grafos:koniginfinity [WikiMat]

====== 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$. ===

{{ :grafos:konig.png?500 |}}

-----

//Demonstração:// Seja $\mathcal P$ o conjunto de todos os caminhos finitos da forma $v f(v) f\big(f(v)\big) ...$ 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 ...$ é, de fato, um raio.