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

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

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.

• Thank you! If $G_\pi$ does not have cycles, it means that it's a forest or I need to add something after that? Jul 25 at 12:28
• A tree is a connected acyclic graph. A forest, is just like a tree, but it doesn't have to be connected. Therefore, a forest is just an acyclic graph Jul 25 at 12:49
• Ok got it. Another last question - for the base of the induction, can I say the following? - Base: for $k=0$ (where $k$ is the DFS step), the graph $G_\pi$ consists of $|V|$ vertices with no edges so each vertex is a tree and $G_\pi$ is a forest consisting of $|V|$ trees. Jul 25 at 13:05
• @vesii yes, that is totally valid Jul 25 at 13:48