is it always true that the depth of BFS is $\leq$ DFS?

Question

I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS?

From what I understand, the tricky part here is the possible cycles in the graph. Even though that I believe that the depth of BFS will always be less or equal to the depth of DFS.

In each iteration of BFS, from what I understand, the depth might grow by one, but DFS's grows in each vertex it can not reach, sometimes above the maximal value of BFS.

So, is it always true that the depth of BFS is $\leq$ DFS?

Answer 1

A result about BFS is that what you call the depth of the BFS of a node $v$ is the length of a shortest path from the source to $v$.

Assume the exists an instance where the depth of the DFS $<$ BFS. Then we have a path from the source to $v$ that has length strictly smaller (the path taken by the DFS to reach $v$) than the length of a shortest path from the source to $v$ (the path taken by the BFS), which is impossible.

This argument by contradiction shows that depth BFS $\leq$ DFS, for any graph.