Paths of Minimal Length from Vertex form Tree

Theorem

Let $G = \struct {V, E}$ be a simple graph.

Let $r \in V$ be a vertex in $G$.

Let $P$ be the set of minimal length paths beginning at $r$.

Let $p, q \in P$.

Let $E'$ be defined as follows:

$\set {p, q} \in E'$ if and only if either:

$q$ is formed by extending $p$ with one edge of $E$ and one vertex of $V$

or:

$p$ is formed by extending $q$ with one edge of $E$ and one vertex of $V$.

Then $T = \struct {P, E'}$ is a tree.

Proof

Let $\tuple r$ be the $0$-length $G$-path whose only vertex is $r$.

Connected

We will show that there is a $T$-path from $\tuple r$ to each element $p$ of $P$.

We proceed by induction on the length of $p$.

Let $p$ have length $0$.

Then by definition:

$p = \tuple r$

Thus the $0$-length $T$-path $\tuple {\tuple r}$ connects $\tuple r$ to $p$.

This article, or a section of it, needs explaining. In particular: Is $\tuple {\tuple r}$ meant here or just $\tuple r$? If the former, explain the meaning of the double brackets. In fact, what exactly is a $T$-path? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Suppose that there is a $T$-path from $\tuple r$ to each element of $P$ of length $n$.

Let $p \in P$ have length $n + 1$ and final vertex $z$.

Let $p^*$ be the $G$-path obtained from $p$ by removing the last vertex and the last edge.

Then $p^*$ is a $G$-path of length $n$.

We must show that $p^* \in P$.

Let $w$ be the last vertex of $p^*$.

Aiming for a contradiction, suppose $p^* \notin P$.

Then by definition of $P$, there is a $G$-path $m$ from $r$ to $w$ which is shorter than $p^*$.

But then appending the last edge and vertex of $p$ to $m$, one obtains a $G$-path from $r$ to $z$ which is shorter than $p$.

This contradicts the supposition that $p \in P$.

Thus we conclude that $p^* \in P$.

By the inductive hypothesis, there is a $T$-path $b$ from $\tuple r$ to $p^*$.

Then by definition of $E'$, there is an edge from $p^*$ to $p$.

Appending that edge and $p$ to $b$ yields a $T$-path from $\tuple r$ to $p$.

As such a $T$-path exists for each $p \in P$, $T$ is connected.

$\Box$

Acyclic

This needs considerable tedious hard slog to complete it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.