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)

Question

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!

Answer 1

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