1
$\begingroup$

Let $G = (V,E)$ be undirected and connected graph and let $u\in V$. Let $DFS(u)$ and $BFS(u)$ be trees of searching $G$ by algorithms DFS and BFS respectively(starting from $u$). Prove that: $DFS(u)=BFS(u)\Leftrightarrow G \text{ is a tree}$

implication $\Leftarrow$) is obvious but I don't know how to prove $\Rightarrow$). Graph theory is a field where I, unfortunately, often make terrible mistakes. I don't know how to show it strictly. Can anyone help?

  • 0
    I tried this, but I failed. If$G$is not a tree, then it has a cycle. Results of DFS and BFS on a cycle are different, that's for sure. But only if we use those algorithms with the same starting vertex, so if $u$ isn't in a cycle, then these algorithms can start exploring some cycle from different vertices I think. I don't know what to deal with this.2012-12-30

1 Answers 1

2

Suppose $G$ is not a tree, and we're given a spanning tree $T$ and the starting node $u$, and we want to decide whether $T$ comes from a breadth-first search or a depth-first one.

Call an edge "funky" if it is part of some nontrivial cycle. Consider subgraph of $G$ consisting of all funky edges, and divide the vertices of $G$ into funkily connected components. A bit of thought ought to convince you that the entire $G$ must be a tree of funkily connected components, where every non-funky edge must connect two different f.c.c.s. Every spanning tree (no matter where it comes from) must consist of all the nonfunky edges, plus an internal spanning tree in each f.c.c.

Since $G$ is not a tree, there is at least one f.c.c. with more than one vertex in it. Choose such an f.c.c and call it $F$; that is where the entire rest of the argument plays out.

Now, there must be one particular node in $F$ where the search algorithm enters $F$. If $u$ is in $F$, that is it. Otherwise it is the node at the $F$ end of the last non-funky edge in a path from $u$ to $F$ -- this is unique, because if there were two different such non-funky edges, they would have been funky! Call the entering node $v$.

So our unknown search algorithm has necessarily entered $F$ at $v$. The entrance node $v$ must have more than one neighbor in $F$, since if it had only one neighbor in $F$, the edge to that neighbor couldn't be funky, which is a contradiction.

Now, if $T$ comes from a BFS, all of $v$'s neighbors in $F$ must automatically also be its neighbors in $T$, because when the BFS arrived at $v$, this was the first encounter the search algorithm ever had with $F$.

On the other hand, if $T$ comes from a DFS ... can you take it from here?