I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. I was having a little difficulty in understanding the steps of the proof and hence I made an attempt to understand it fully by accompanying each statement in the proof with a possible graph of the situation.
Theorem 22.10 : In a depth-first search of an un-directed graph $G$, every edge of $G$ is either a tree edge or a back edge.
Proof:
Let $(u , v)$ be an arbitrary edge of $G$, and suppose without loss of generality that $d[u] < d[v]$. Then, $v$ must be discovered and finished before we finish $u$ (while $u$ is gray), since $v$ is on $u$'s adjacency list.
If the edge $(u, v)$ is explored first in the direction from $u$ to $v$ , then $v$ is undiscovered (white) until that time.
Figure 1 : Situation in point 2. DFS starts from 'u', 'u' is grayed and DFS then looks along the red arrow to 'v'
- Otherwise we would have explored this edge already in the direction from $v$ to $u$. Thus, $(u, v)$ becomes a tree edge.
Figure 2 : Situation in point 3. DFS starts from 'u', 'u' is grayed, then discoveres 'w' and 'w' is grayed and then again discovers 'v' DFS then looks along the red arrow to 'u' , the green pointer explains the rest
- If $(u, v)$ is explored first in the direction from $v$ to $u$, then $(u, v)$ is a back edge, since $u$ is still gray at the time the edge is first explored.
Figure 3 : Situation in point 4. DFS starts from 'u', 'u' is grayed, then discoveres 'w' and 'w' is grayed and then again discovers 'v' DFS then looks along the red arrow to 'u' , 'u' is already grayed so the edge becomes a back edge, indicated by the green pointer
■
Could anyone confirm if I am on the right track or if not please rectify me.
[My question might seem similar to this or this but neither of them seemed to help me]
