White Path Lemma

Seen in CS341.

Claim ("white path lemma")

When we start exploring a vertex $v$, any $w$ that can be connected to $v$ by an unvisited path will be visited during explore($v$).

Proof:

Basic Property

Claim

If $w$ is visited during explore($v$), there is a path $v\to w$.

Proof: Same as BFS