Shortest Path on Specific Graph with one Property !?

Question

I stuck in one challenging question, I read on my notes.

An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this graph, the shortest path between any two vertices is on the minimum spanning tree (MST). Verify the following:

1) shortest path between any two vertices $u$, $v$ is unique.

My question is, is this statement (1) is false or True?

Other details is not mentioned in the old exam question, But I think:

if we consider Any shortest path must be on MST The statement is True, if consider there exists a shortest path on MST this is false.

Answer 1

Let G be an undirected, weighted, connected graph G. Let $u$ and $v$ be two non-adjacent vertices, and let d$(u,v) = k$. Also, let $P_1 = (u,u_1,...u_{k-1},v)$. Now, assume to the contrary that $\exists$ a path, distinct from $P_1$, from $u$ to $v$ of length $k$. That is, $P_2 = (u,w_1,w_2,...w_{k-1},v)$. Then, by assumption, $P_1$ is contained in the minimum spanning tree as well as $P_2$. However, the minimum spanning tree then contains the cycle $C = (u,u_1,...u_{k-1}, v, w_{k-1},w_{k-2},...w_1,u)$, a contradiction. So, it must be the case that the shortest path between any two non adjacent vertices is unique.

Answer 2

If the MST is unique then the answer of user3440448 is correct. Since your notes say "the MST" this seems to be the case. However, note, that if the MST is not unique then statement (1) does no longer hold:

Consider a cycle of four nodes $v_1$, $v_2$, $v_3$, and $v_4$ with length 1 for all edges $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$, and $(v_4, v_1)$. Obviously, choosing any three edges gives a MST and there are two shortest paths from $v_1$ to $v_3$: $(v_1, v_2) - (v_2, v_3)$ and $(v_1, v_4) - (v_4, v_3)$. Both of these paths are contained in a MST (but they cannot be contained in the same MST).

This shows that in general, if every shortest path is contained in a MST, the paths need not be unique.