Prova da propriedade DFS das componentes aresta-biconexas

[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 sub­grafo de F induzido pelo conjunto de vértices de K é uma árvore radicada.

Prova

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 rx 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 rx. 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 uz está todo fora de K exceto pelos dois extremos. Seja Q um caminho em K de zu. Os caminhos P e Q não têm arcos em comum e portanto a concatenação de PQ é 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.