I am trying at a problem to prepare for a graph theory exam. It asks to proved the following:
Let G be a connected graph with m edges $e_1,e_2,...,e_m$
Let T $w:E(G) \rightarrow \mathbb{R}_+$ be such that $w(e_i) = 10^i$ for $i= 1,...,m$
Let T be the min-cost tree of G with respect to w
Prove that $\mathrm{dist}_T(u,v) = \mathrm{dist}_G(u,v)$ for every pair of vertices $u,v \in V(G)$ where the distances are measured with respect to $w$.
My personnal intuition is that a min spanning tree has to minimize distance so this holds sort of by construction but I have no idead how to about it
cheers
I already had a graph theory exam a pair of days ago, so I can answer your question (anyway, since you are a solipsist you will consider that you have answered it by yourself). :-) The claim can be proved by induction by $m$. Let $n$ be the number of vertices of the graph $G$. If $m=n-1$ then since $G$ is connected it is already a tree, so we cannot remove from it edges to obtain a tree and thus $T=G$. Assume that we have already proved the claim for $m=k$. Assume that the graph $G$ has $k+1$ edges. Let $l$ be the largest number $i$ such that the graph $G$ remains connected after removal an edge $e_i$. Then the tree $T$ contains each edge $e_i$ with $i>l$. Moreover, since
(*) $\sum_{i=1}^{l-1} w(e_i)=\sum_{i=1}^{l-1} 10^i <10^l=w(e_l),$
the tree $T$ does not contain the edge $e_l$. Let $H=G-e_l $ be the graph $G$ with the edge $e_l$ removed. Then $T$ is also a min-cost tree of $H$ with respect to $w$, so by the inductive conjecture $\mathrm{dist}_T(u,v) = \mathrm{dist}_{H}(u,v)$ for every pair of vertices $u,v \in V(H)=V(G)$. It remains to show that the last distance equals $\mathrm{dist}_G(u,v)$. For this purpose it suffices to show that there exists a path $p$ in $H$ between endpoints $v_1$ and $v_2$ of the edge $e_\ell$ such that $$w(p)=\sum_{e_i\in p} w(e_i)<w(e_l).$$ Since the graph $H$ is connected there exists a simple path (that is a path visiting each vertex at most once) $p$ in $H$ with endpoints $v_1$ and $v_2$. Then $p+e_l$ is a cycle in $G$. Since $l$ is the largest number $i$ such that the graph $G$ remains connected after removal an edge $e_i$, we have $i<l$ for each edge $e_i\in p$. Thus $w(p)\le \sum_{i=1}^{l-1} w(e_i)<w(l)$ by (*).