In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest

Question

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 if DFS-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\} $$

Answer 1

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm.

The key point, is that a forest is a graph without cycles. So basically, you want to show that no new cycles where created in the last step. To prove this, you will want to have a statement similar to this:

Assume towards contradiction that $G_{\pi'}$ contains a cycle. Hence, the new node $u'$ that was added to $G_{\pi}$ in order to create $G_{\pi'}$ must be a part of the new cycle (since $G_{\pi}$ was a forest). Therefore, there must be some node $u\in G_\pi$ such that $\pi(u)=u'$, but this is impossible since it would mean that $u'$ would have been already visited in $G_{\pi}$, but this is impossible since $u'$ was visited only after $G_{\pi}$ was constructed.