# 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)

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!

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$$).

• Note that $v$ and $s$ are different... Nov 4, 2021 at 10:17
• @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. Nov 4, 2021 at 10:20
• In this case, when $v=s$ there is a counter example, I agree. But what happens when $v \ne s$? Nov 4, 2021 at 10:28
• @user144930 I edited my answer. Nov 4, 2021 at 10:44
• 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? Nov 5, 2021 at 8:35