Question

A clique is a graph in which all pairs of nodes are connected by an edge. Suppose that you run DFS on a clique. What is the depth of the DFS tree? Prove your answer.

Answer 1

Ans :

When we run DFS on a clique, the depth of the DFS tree would be (V-1), where V is the number of vertices in the clique.

Proof:

Since in a clique, each pair of vertices are connected together by an edge, at each step of the dfs the current visited node will be able to take us to some other unvisited node untill all nodes are visited. Hence this process will continue for (V-1) times untill all nodes are visited.

Hence the depth of the DFS tree would be (V-1).

For example, for the following clique the dfs tree if would look like:

We can clearly see that depth of this tree is 3, i.e., (number of vertices-1) = (4-1) = 3.