[Enunciado do exercício] Seja F uma floresta DFS de um grafo não-dirigido G. Seja K uma componente aresta-biconexa 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 em F durante a execução de dfsR(G,r). Isso mostra que todos os vértices de K tornam-se descendentes de r em F.
Agora tome um vértice x de K e seja P um caminho em F de r a x. O primeiro e o último vértices de P estão em K. Mas suponha, por um momento, que nem todos os vértices de P estão em K. Seja v o primeiro vértice de P fora de K, ou seja, em alguma componente aresta-biconexa diferente de K. Seja u o pai de v. Seja z o primeiro vértice de P depois de v que está em K. O segmento de P que vai de u a z está todo fora de K exceto pelos dois extremos. Seja Q um caminho em K de z a u. Os caminhos P e Q não têm arcos em comum e portanto a concatenação de P e Q é um circuito. Todos os vértices do circuito estão em K. Em particular, todos os vértices de P estão em K, o que contradiz a hipótese que adotamos há pouco. A contradição mostra que todos os vértices de P estão em K.