0
$\begingroup$

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph.

True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning tree resulting from BFS(s).

I assume that this one is True, and I think that because if $v$ is a leaf in every DFS(s), that means $v$ has no children on $G$ graph, but I struggle to prove it.

I'd like to get some help.

Thanks a lot!

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Note that $v$ is a leaf in the spanning tree given by BFS($v$) if and only if $v$ is a leaf in $G$ (by definition of BFS).

That said, you should try with a graph $G$ that is a circular graph (or cycle graph), and any vertex $v=s$.

If you want an answer when $v \neq s$, then we can indeed show that if $v$ is a leaf in any DFS($s$), then $v$ is a leaf in $G$ (and so $v$ is a leaf in any BFS($s$)).

Indeed, suppose $v$ is not a leaf in $G$. Then it means that $v$ has two neighbors $x$ and $y$. If we suppose that $v$ is a leaf in any DFS($s$), then consider such a DFS where $x$ is explored before $y$. We have now two possibilities:

  • $v$ is explored before $x$. Since $v\neq s$, that means that $v$ is not a leaf in the resulting spanning tree (because in this tree, $v$ has two neighbors);
  • $v$ is explored after $x$. Then a graph traversal similar to this one until $x$, which then explores $v$ then $y$ then continues the DFS from $y$ would still be a DFS. In the resulting spanning tree, $v$ has two neighbors, so $v$ is not a leaf.

We proved that $v$ not a leaf in $G$ implies there exists a DFS($s$) where $v$ is not a leaf, or equivalently $v$ is a leaf in every DFS($s$) implies $v$ is a leaf in $G$ implies $v$ is a leaf in every DFS($s$).

$\endgroup$
10
  • $\begingroup$ Note that $v$ and $s$ are different... $\endgroup$
    – user144930
    Nov 4, 2021 at 10:17
  • $\begingroup$ @user144930 Since you wanted the result for any $v$ and any $s$, a counter-example in the particular case of $v = s$ can still help you. $\endgroup$
    – Nathaniel
    Nov 4, 2021 at 10:20
  • $\begingroup$ In this case, when $v=s$ there is a counter example, I agree. But what happens when $v \ne s$? $\endgroup$
    – user144930
    Nov 4, 2021 at 10:28
  • $\begingroup$ @user144930 I edited my answer. $\endgroup$
    – Nathaniel
    Nov 4, 2021 at 10:44
  • $\begingroup$ Can someone explain this point to me again, please? *v is explored after x. Then a graph traversal similar to this one until x, which then explores v then y then continues the DFS from y would still be a DFS. In the resulting spanning tree, v has two neighbors, so v is not a leaf. Also, why is that matter that v != s? $\endgroup$ Nov 5, 2021 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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