Return to Answer

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me follow your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, for all $0\le i\le k-1$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by a path in $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by a path in $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me follow your approach. Let $K(t)$ be the edges of $G(D)$ that have been determined to be part of $T'$, where $t$ is any point of time during Kruskal's algorithm on $G(D)$.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$. At the point of time $t_0$ when edge $(u,v)$ was determined to be part of $T'$ but not added yet by Kruskal's algorithm, $(u_i, u_{i+1})$, an edge of smaller length must have been tried, which meant node $u_i$ and node $u_{i+1}$ must have been connected by $K(t_0)$. That means before $t_0$, node $u$ and $v$ had been connected by $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me follow your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

Let vertices of $G(D)$ be $V=\{1,2,\cdots, n\}$, which are also vertices of $T$.

For the sake of contradiction, suppose edge $(i,j)$ is not in $T$ but in $T'$. Let $P=(v_0=i, v_1, \cdots, v_k=j)$ be the unique path from node $i$ to node $j$ in $T$ where $k\gt1$. Note that $D_{ij}=\sum_{(u,v)\text{ is an edge in }P}w((u,v))$, where $w>0$ is the weight (length) function on edges of $T$.

Consider the edge set $N=T'\setminus\{(i,j)\}\cup\{\text{edges of }P\}$. $N$ is $T'$ with edge $(i,j)$ replaced by path $P$. So $V$ is still connected by $N$. Moreover, the number of edges in $N$ is $(n-1)-1+k>n-1$. Let $N'$ be a spanning tree of $N$, which has $n-1$ edges. $V$ is still connected by $N'$. However, the difference between the total weight of $N'$ and that of $T'$ in $G(D)$ is $$\begin{aligned} w(N')-w(T')&\lt w(N)-w(T')\\ &=\sum_{(u,v)\text{ is an edge in }P}D_{uv} -D_{ij}\\ &= \sum_{(u,v)\text{ is an edge in }P}(D_{uv}-w((u,v)))\\ &\le 0, \quad(\text{ in fact, } D_{uv}=w((u,v))\text{ since } (u,v)\text{ is in }T) \end{aligned}$$ which contradicts that $T'$ is a minimum spanning tree of $G(D)$.

Hence, all edges of $T$ are in $T'$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me follow your approach. Let $K(t)$ be the edges of $G(D)$ that have been determined to be part of $T'$, where $t$ is any point of time during Kruskal's algorithm on $G(D)$.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$. At the point of time $t_0$ when edge $(u,v)$ was determined to be part of $T'$ but not added yet by Kruskal's algorithm, $(u_i, u_{i+1})$, an edge of smaller length must have been tried, which meant node $u_i$ and node $u_{i+1}$ must have been connected by $K(t_0)$. That means before $t_0$, node $u$ and $v$ had been connected by $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.