[Enunciado do exercício] Seja F uma floresta DFS de um grafo G. Seja K uma componente forte de G. Queremos provar que o subgrafo de F induzido pelo conjunto de vértices de K é uma árvore radicada.
Seja r a cabeça de K. Basta mostrar que todos os vértices de K são descendentes de r em F e que, para cada vértice x de K, todos os vértices no caminho de r a x em F estão em K.
Seja x um vértice de K. Seja C um caminho de r a x em K. Quando começou a execução da encarnação dfsR(G,r) da função função dfsR(), nenhum vértice de K havia sido descoberto. Em particular, nenhum vértice de C havia sido descoberto. Logo, todos os vértices de C tornaram-se descendentes de r F durante a execução de dfsR(G,r). Isso mostra que todos os vértices de K são descendentes de r em F.
Agora tome um vértice x de K e seja P um caminho de r a x em F. Como x está em K, existe um caminho, digamos Q, de x a r em K. A concatenação de P com Q é um passeio fechado e portanto todos os seus vértices estão em K. Em particular, todos os vértices de P estão em K.