# Is there a way to check if a path in a graph is infinite?

Edit: Maybe this is not the best title, so few free to change it.

So I'm trying to prove the following statement:

A finitely branching tree $T$ with infinitely many vertices must have an infinite path.

My proof is loosely like this:

1. $P = \emptyset$

2. Start at the root $v_0$

3. Since there are infinitely many vertices, there must be some vertice with infinitely successors.

Order the successors of $v_0$ (there is a finite number of them), with the vertices with infinite successors to the left.

$P = P \cup \{v_0\}$

Select $v_1$ as the new root and repeat (3).

What bothers me the most is that I didn't manage to find a deterministic way to do step (3), at first I though BFS would work, since it's complete it would eventually visit all vertices at height $n$ and I could use this to construct an arbitrarily long path $P_n$, however arbitrarily long and infinite are two different things.

• This is indeed not the best title, change it to what you want to proove, it will be clearer – user5751924 Dec 10 '16 at 2:24