Question

Either prove or give a counterexample: if {u,v}is an edge in an undirected graph, and during depth-first search (u)<post (v), then vis an ancestor of uin the DFS tree.

Short answer

If {u,v} is an edge in an undirected graph, and during the depth-first search post (u) < post(v) , then v is an ancestor of u in the DFS tree.

Step-by-step solution

Depth-first search

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in the downward direction one by one.

Some properties ofdepth-first search are as follows:

1. Using DFT we can verify whether the graph is connected or not it means it detects the cycle present in the graph or not.
2. We can find out the number of connected components by using adepth-first search.
3. Here we are using the stack as a data structure.

The time complexity of the list is O(V+E).

The time complexity of matrix is$\mathrm{O}\left({\mathrm{V}}^2\right)$.

It contains various edges, they aretree edge, forward edge, back edge, or cross edge all the edges are explained below:

Tree edge: The graph obtained by traversing while using a depth-first search is called its tree edge.

Forward edge: the edge {u,v} whereis a descendant and it is not part of the depth-first search is called the forward edge.

Back edge: the edge {u,v} where is the ancestor and it is not part of the depth-first search is called the back edge.

Step 2: During DFS,post (u) < (v) , and v is an ancestor of u in the DFS tree

Consider the depth first search tree of graph G starting at any vertex. For this graph, if depth-first search is performed in the graph then if post is less than post v than, here the edge {u,v} where u is ancestor and it is not part of depth first search is called back edge. If {u,v} is an edge in an undirected graph and while performing a depth-first search in the undirected connected graph the the post (u)< post (v) , then v is an ancestor of in the DFS tree.

Here it follows these two conditions:

1. [preu,post u] [prev.post v ]
2. [prev,[preu,post u]post v ]

Only these options are taking place here for an undirected graph post u is less than post v. since there is an edge between these two vertices and option one is not possible because it is a must to traverse all the neighbors of a vertex before marking it as visited.

So, option two’s condition is only possible which defines the vertex v is the ancestor of u. hence an undirected graph, and during the depth-first search, post(u) < post (v),then v is an ancestor of u in the depth-first search traversal.