For every tree of shortest path there is a way of writing the adjacency lists such that there is a BFS thet returns this tree?

Question

A directed graph G=(V,E) is given and I am asked to prove if there is a tree of shortest path of this graph that cannot be returned using BFS. Meaning to say if it is true or not that for every tree of shortest path a BFS can return it. I thought that the answer is true, for every tree of shortest path there is a way of arranging the adjacency lists of G such that a BFS can return this tree, but I cannot find a mathematical way of proving it. Or maybe it is false, meaning there is a counter example of a tree of shortest path that cannot be returned by BFS but I can't find this example either. I would appreciate some help, thanks!

Answer 1

Let $s,x \in V$ be two vertices and $P$ a shortest path from $s$ to $x$ in $G$. Set $k := \text{length}(P)$. We prove the statement via induction on $k$. If $k = 1$, then $(s,x) \in E$ and BFS can start with this edge.

Now assume that $k \geq2$. Let $y \in V$ be the last vertex before $x$ on $P$. Run BFS until all vertices of distance $\leq k-1$ from $s$ are reached (this includes $y$). By the induction hypothesis, this run of BFS can be chosen such that the subpath $P_{[s,y]}$ was found. Finally, BFS can continue with the edge $(y,x)$ when starting to add visit all vertices of distance $= k$ from s. Hence, $P$ is contained in the BFS-tree that will be returned.