shortest path MST

54 Views Asked by At

Let $G=(V,E)$ be a undirected graph and $w:E\rightarrow \mathbb R$ a weight function. If the shortest path between two adjacent vertices is the connecting edge then there is a minimum-spanning tree containing this edge.
I think this is true but how can I prove it?

1

There are 1 best solutions below

0
On BEST ANSWER

Let \begin{align} V&=\{v_1,v_2,v_3\}\\ E&=\{\{v_1,v_2\},\{v_2,v_3\},\{v_1,v_3\}\}\\ w(\{v_1,v_2\})&=3\\ w(\{v_2,v_3\})&=w(\{v_1,v_3\})\\ &=2\ . \end{align} What is the shortest path between vertices $\ v_1\ $ and $\ v_2\ $ in this weighted graph? What are its minimal spanning trees?