[Enunciado do exercício] Seja F uma floresta DFS de um grafo G. Seja v um vértice e w um filho de v em F. Queremos provar que lo[v] ≤ lo[w].
Prova: Suponha inicialmente que nenhum arco abraça w. Então lo[w] ≡ pre[w]. Como lo[v] ≤ pre[v] e pre[v] < pre[w], temos lo[v] < lo[w], como queríamos demonstrar.
Suponha agora que algum arco x-y abraça w. Escolha x-y de tal modo que lo[w] ≡ pre[y]. Considere os dois casos a seguir.
Caso 1: pre[y] ≥ pre[v]. Então y é descendente de v. Nesse caso, lo[v] ≤ pre[v] ≤ pre[y] e portanto lo[v] ≤ lo[w], como queríamos demonstrar.
Caso 2: pre[y] < pre[v]. Nesse caso, y não é descendente de v. Para provar que x-y abraça v, mostraremos a seguir que existe um caminho de y até um ancestral próprio de v. Como x-y abraça w, existe um caminho de y a um ancestral próprio de w. Em particular, existe um caminho de y a v. Como existe um caminho de v a y, os vértices y e v estão na mesma componente forte. Seja r a cabeça da componente. De acordo com a propriedade DFS das componentes fortes, v é descendente de r. Como r é cabeça, temos pre[r] ≤ pre[y], donde pre[r] < pre[v], e assim r ≠ v. Logo, r é ancestral próprio de v. Como y e r estão na mesma componente forte, existe um caminho de y a r. Era o que faltava para provar que x-y abraça v. Portanto, lo[v] ≤ pre[y], donde lo[v] ≤ lo[w], como queríamos demonstrar.