# Is a predecessor subgraph always connected?

Given an undirected graph $$G$$ with non-negative edge weights, how can we prove that the predecessor subgraph $$G_{p}$$ of $$G$$ is always connected?

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

I've read that the predecessor subgraph forms a tree, but in the context of that claim, it was assumed the predecessor subgraph is connected and $$|E_{p}| = |V_{p}| - 1$$.

Can anyone offer a proof that the predecessor subgraph $$G_{p}$$ of a graph $$G$$ is always connected (or disprove the claim)?

• I'm assuming that you're dealing with undirected graphs with non-negative edge weights, and you are interested in the predecessors from a single source vertex. Is this correct? Sep 21 at 18:05
• Also there are multiple ways to define the predecessor subgraph. Do you want a graph in which you add exactly one edge $(p,v)$ for each non-source vertex $v$ such that $p$ is the predecessor of $v$, or you want to have an edge for each possible predecessor? Are the edges undirected or directed towards $v$? If the edges are directed, what do you mean by "connected"? Sep 21 at 18:17
• In response to your first question: yes, that's correct. For the second, I've updated the question and added the definition of the predecessor subgraph I'm using Sep 21 at 19:04
• $v.p$ is not defined, but I guess it's the parent of $v$ as set by the breadth first search algorithm. Sep 21 at 19:32
• Yes, that's correct Sep 21 at 19:36

Let $$s$$ be your source vertex and let $$d(v)$$ denote the distance from $$s$$ to $$v$$. Let $$v_1, \dots, v_n$$ be the vertices of your graph in non-decreasing order of distances from $$s$$.
You can show by induction on $$i$$ that the subgraph $$G_i$$ of $$G_p$$ induced by $$\{v_1, \dots v_i\}$$ is connected.
The base case is trivial as $$G_1$$ contains only $$v_1=s$$.
Consider now $$i>1$$. It suffices to argue that $$G_i$$ contains an edge $$(v_j, v_i)$$ for some $$j. By definition, the predecessor $$p(v_i)$$ of a vertex $$v_i$$ (w.r.t. the source $$s$$) ensures that there is a shortest path from $$s$$ to $$v_i$$ that first goes from $$s$$ to $$p(v_i)$$ and then traverses the edge $$(p(v_i),v)$$. Since edge-weights are non-negative, $$d(p(v_i)) < d(v_i)$$ which shows that $$p(v)=v_j$$ for some $$j.
Since your graph has exactly $$n-1$$ edges and it is connected, it is actually a tree.
• Can you explain why it suffices to argue that $G_i$ contains an edge $(v_j, v_i)$ for some $j<i$? Sep 25 at 21:22
• By induction hypothesis the subgraph $G_{i-1}$ induced by $v_1, v_2, \dots, v_{i-1}$ is connected. If there is an edge from any of these vertices $v_j$ to $v_i$ then $G_i$ is connected too. A path from $v_h$ (with $h < i$) to $v_i$ in $G_i$ can be obtained by concatenating a path from $v_h$ to $v_j$ in $G_{i-1}$ (which is connected) with the edge $(v_j, v_i$). A path from $v_i$ to $v_h$ in $G_i$ can be obtained by concatenating the path consisting of the sole edge $(v_i, v_j)$ with a path from $v_j$ to $v_h$ in $G_{i-1}$ (which is connected). Sep 25 at 23:00