Let G be a directed graph. Let s be a ‘start vertex’. An infinite path of G is an infinite sequence v0, v1, v2, ... of vertices such that v0 = s and for all i> 0, there is an edge from vi to vi+1. In other words, this is a path of infinite length. Because G has a finite number of vertices, some vertices in an infinite path are visited infinitely often.

1. If p is an infinite path, let Inf(p) be the set of vertices that occur infinitely many times in p. Prove that Inf(p) is a subset of a single strongly connected component of G.

2. Describe an algorithm to determine if G has an infinite path. Prove that it is correct.