📂Graph Theory

Proof of Kőnig's theorem

Theorem ¹

Let $G$ be a locally finite connected graph. Then, for every $v \in V(G)$, there exists a one-way infinite path with $v$ as its starting point.

Proof

Since $G$ is a connected graph, for all $z \in V(G)$ other than $v$, there are infinitely many paths from $v$ to $z$. And since $G$ is locally finite, among these infinitely many paths, infinitely many must start with the same edge, let’s call this edge $vv_{1}$. Similarly, a new edge, $v_{1}v_{2}$, can be chosen. This way, the following one-way infinite path is obtained. $$ v \to v_{1} \to v_{2} \to \cdots $$

■