3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ @LeenDroogendijk Your answer was very nice, why have you deleted it? $\endgroup$
    – dtldarek
    Oct 15 '13 at 6:44
  • $\begingroup$ Thank you for explaining this. I should have noted in the assumption that the graph is undirected and that we generally do not observe multigraphs. $\endgroup$
    – Alex
    Oct 15 '13 at 7:05
  • $\begingroup$ @AlexMardikian I'm not sure if you have seen the answer of LeenDroogendijk: he was talking about cycles and order in which both algorithms discover the vertices of a cycle. I think that this path would make even a nicer proof than mine. $\endgroup$
    – dtldarek
    Oct 15 '13 at 7:09
  • $\begingroup$ I didn't see his answer before posting, but I will consider it that way too. I wasn't thinking at all about how having one more edge in $G$ would require a cycle to exist. $\endgroup$
    – Alex
    Oct 15 '13 at 7:20
  • $\begingroup$ My answer was not good enough, but I will improve it a bit, then undelete it. $\endgroup$ Oct 15 '13 at 9:37
2
$\begingroup$

Note that it is essential that the trees are rooted trees. If you start with a paw (a triangle with an attached edge, so this certainly is not a tree) the BFS-tree from the vertex with degree 1 is a claw and the DFS-tree from a vertex with degree 2 is also a claw for one of the choices of the second vertex. This suggests that your proof must involve the root somehow.

If $G$ and $T$ are not equal, then $G$ must contain a cycle. Let $v$ be a vertex that is on a cycle and has minimum distance to the root $u$ ($v$ and $u$ may be equal). Let $v=v_1,\ldots,v_n,v$ be an actual cycle through $v$. Prove, using the BFS description that both $vv_2$ and $vv_n$ must be edges of $T$. Prove, using the DFS description that $vv_2$ can $vv_n$ cannot possibly be both edges of $T$.

$\endgroup$
2
  • $\begingroup$ If $v$ is at the same BFS-level as $v_n$ they must have a common "ancestor" at a lower BFS-level. This common ancestor is on a cycle, contradicting the assumption that $v$ is a vertex on a cycle that has minimum distance to the root. $\endgroup$ Oct 15 '13 at 11:18
  • $\begingroup$ Indeed. Well, you are correct, and I should have read more carefully. (I like your approach more than mine.) $\endgroup$
    – dtldarek
    Oct 15 '13 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.