[Math] Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent

algorithmscomputer sciencegraph theory

Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to show that $T = G$.

My main problem for this is that I am not sure how to initially approach this proof, and given my current approach is within reason I am stuck as for my next step.

My current thought is to go by contradiction and suppose that $T$ is both the DFS and BFS tree of $G$ with $u$ being the root, but $T \neq G$. As $T \subset G$, there must exist an edge $e \in G$ such that $e \notin T$ (since $G$ is connected it cannot be the case that there is a vertex in $G$ that is not in $T$). From here I believe my contradiction will come from the DFS and BFS traversals not being equivalent, but this is where I am stuck in this approach.

Could anyone hint at my next step or give me an idea for another approach to the proof?

Best Answer

Hint:

It is not true for directed graphs, that is, there exists a directed graph $G$ and a DFS run and a BFS run such that both trees are the same, but $G$ is not a tree. An example might be a back-edge.
In the case of undirected graphs it still might not be true, e.g. if the graph is non-simple, i.e. it allows more than one edges between two vertices.
It is true, if the graph is simple, connected and undirected, and the very basic observation is that $G$ is a tree if and only if every edge was traversed in the BFS/DFS search.
Suppose that $T_{BFS} = T = T_{DFS}$, but that there is $e \in E(G) \setminus E(T)$, that is, an edge that was not visited by any of the algorithms. The only reason the edge was not traversed could be that the vertex on the other side was already visited, but if there is a DFS-back-edge then BFS must have used it before.

I hope this helps $\ddot\smile$

Related Solutions

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

Your solution looks good to me!

I have one suggestion if you consider directed graphs. Consider the graph:

A -> B -> C
D -> F

Let's say your algorithm starts arbitrarily at node B. It will traverse the graph through B and C and mark them as connected components - but it won't catch A!

A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.

This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B and produces the set {B, C}. Then, let's say that the algorithm arbitrarily selects A as its next starting point. When it traverses the graph to B, it should union the new set of connected components {A} with the already-existing set {B, C} instead of simply skipping node B.

In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.

[Math] Show that the depth of a BFS tree can’t be larger than the depth of a DFS tree while they’re operate on the same vertex

Your proof seems to be getting at the right idea, but there are a few details missing that are important for a clear writeup. In order from most to least important:

You say that your second case is a proof by contradiction, but you never say what assumption you are making that leads to a contradiction.
The definition of the cycle and the "back edge" on it is under-specified. I assume from context that you're saying that there's specifically an edge $yx$ that's not part of $T_{DFS}$, from which we may conclude that $x$ lies somewhere on the path from $s$ to $y$ in $T_{DFS}$.
The notations $d(x,y)$ and $\delta(x,y)$ seem ambiguous given that there are three, not two, different distances between vertices to keep track of: the distance in $G$, the distance in $T_{DFS}$, and the distance in $T_{BFS}$. (You also have not said which of these are $d$ and which are $\delta$, but perhaps this has been decided for you if you're doing homework for a specific class.) As a result, your concluding inequality makes no sense.

Also, there is a much simpler argument: if $T_{BFS}$ has depth $d$, it is because there is a vertex $t$ at distance $d$ from $s$ (in $G$). This vertex cannot be at a depth smaller than $d$ in any other tree (any other spanning tree of $G$ rooted at $s$), because there is no path from $s$ to $t$ of length $d-1$. So all other spanning trees of $G$ rooted at $s$, including $T_{DFS}$, must have depth at least $d$.

Best Answer

Related Solutions

[Math] How to use BFS or DFS to determine the connectivity in a non-connected graph

[Math] Show that the depth of a BFS tree can’t be larger than the depth of a DFS tree while they’re operate on the same vertex

Related Question