# Question about step in proof that predecessor subgraph forms a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:

Theorem 22.5: (Correctness of breadth-first search)

Let $$G = (V, E)$$ be a directed or undirected graph, and suppose that $$BFS$$ is run on $$G$$ from a given source vertex $$s \in V$$. Then, during its execution, $$BFS$$ discovers every vertex $$v \in V$$ that is reachable from the source $$s$$, and upon termination, $$v.d = \delta(s, v)$$ for all $$v \in V$$. Moreover, for any vertex $$v \neq s$$ that is reachable from $$s$$, one of the shortest paths from $$s$$ to $$v$$ is a shortest path from $$s$$ to $$v.\pi$$ followed by the edge $$(v.\pi, v)$$.

$$\delta(s,v) \rightarrow \text{length of the shortest path from s to v} \\\ v.d\rightarrow \text{distance assigned to vertex v from s by BFS}\\\ v.\pi\rightarrow \text{predecessor of v in the path from s to v in the BFS}$$

For a graph $$G = (V, E)$$ with source $$s$$, the predecessor subgraph of $$G$$ is $$G_{\pi} = (V_{\pi}, E_{\pi})$$, where $$V_{\pi} = \{ v \in V : v.\pi \neq NIL\} \cup \{s\}$$ and $$E_{\pi} = \{ (v.\pi, v) : v \in V_{\pi} - \{s\}\}$$

The predecessor subgraph $$G_{\pi} = (V_{\pi}, E_{\pi})$$ is a breadth-first tree if $$V_{\pi}$$ consists of the vertices reachable from $$s$$ and, for all $$v \in V_{\pi}$$, the subgraph $$G_{\pi}$$ contains a unique simple path from $$s$$ to $$v$$ that is also a shortest path from $$s$$ to $$v$$ in $$G$$

I have a question about the following proof:

Lemma 22.6:

When applied to a directed or undirected graph $$G = (V, E)$$, procedure BFS constructs $$\pi$$ so that the predecessor subgraph $$G_{\pi} = (V_{\pi}, E_{\pi})$$ is a breadth-first tree.

Line 16 of BFS sets $$v.\pi = u$$ iff $$(u, v) \in E$$ and $$\delta(s, v) < \infty$$ - that is, if $$v$$ is reachable from $$s$$- and thus $$V_{\pi}$$ consists of the vertices in $$V$$ reachable from $$s$$. Since $$G_{\pi}$$ forms a tree, it contains a unique simple path from $$s$$ to each vertex in $$V_{\pi}$$. By applying Theorem 22.5 inductively, we conclude that every such path is a shortest path in $$G$$.

I'm not sure I understand the last sentence of this proof. Can anyone elaborate on how to "apply Theorem 22.5 inductively" to "conclude that every such path is a shortest path in $$G$$"?

Update:

One interpretation might be that we need to use induction to prove the last claim and the last part of Theorem 22.5 about a shortest path from $$v.\pi$$ to $$v$$is used in the proof.

For example, we can order the vertices in $$V_{\pi}$$ in non-decreasing order of distances from $$s$$. The base case would be the first vertex in $$V_{\pi}$$, which is $$s$$. We then assume that it holds for the first $$n$$ vertices in $$V_{\pi}$$ and we show that it holds for $$v_{n+1}$$ by appealing to the last part of Theorem 22.5.

Your update is correct. On first reading I thought it was wrong because distances can be negative. It's early here for me ... then I remembered that CLRS defines distance from $$s$$ to $$v$$ to be the minimum number of edges on any path from $$s$$ to $$v$$ when discussing BFS. Indeed, here is a simple proof:
The proof is by induction on the length (number of edges) of a path from $$s$$ in $$G_\pi$$, with hypothesis $$H(n)$$ that for any path $$P = s \leadsto v \in G_\pi$$ such that the length of $$P$$ is at most $$n$$, $$P$$ is a shortest path in $$G$$. The base case when $$n = 0$$ is trivial. For the step assume $$H(k)$$ for some $$k \in \mathbb{N}$$, let $$n=k+1$$ and let $$P = s \leadsto v.\pi \leadsto v \in G_\pi$$ be a path of length $$k+1$$, where $$s$$ and $$v.\pi$$ may be the same vertex. $$H(k)$$ implies that the path $$P' = s \leadsto v.\pi$$ is a shortest path in $$G$$. Applying Theorem 22.5, we conclude that $$P$$ is also a shortest path in $$G$$, which completes the induction.