Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section:
Depth-first search yields valuable information about the structure of a graph. Perhaps the most basic property of depth-first search is that the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of
DFS-VISIT
. That is, $u=v.\pi$ if and only ifDFS-VISIT(G,v)
was called during a search of $u$’s adjacency list. Additionally, vertex $v$ is a descendant of vertex $u$ in the depth-first forest if and only if $v$ is discovered during the time in which $u$ is gray.
I'm trying to prove the following statement for myself:
In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest.
This question is coming from a booklet published for studding for the finals (without solutions).
I understand the logic behind why it true (with the help of the statements from the book). But I struggle of writing a "formal proof" which shows the correctness of it. Do I need to use induction to prove it (since I need to show it for every step). How to prove this statement formally?
For the completeness of the question, the $G_\pi=(V,E_\pi)$ is the following graph: $$ E_\pi=\{(\pi[v],v)\,:\,\pi[v]\neq NULL \wedge v\in V\} $$