1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I confused with your answer ! you the OP statement say True or False? $\endgroup$ – user153695 Apr 11 '15 at 15:38
  • $\begingroup$ a graph has property that in this graph, the shortest path between any two vertices is on the minimum spanning tree (MST). $\endgroup$ – user153695 Apr 11 '15 at 15:38
  • $\begingroup$ look at the last sentence of my answer... $\endgroup$ – Paddling Ghost Apr 11 '15 at 21:24
  • $\begingroup$ you assume for any shortest path between any two vertices it must be on the minimum spanning tree (MST) $\endgroup$ – user153695 Apr 12 '15 at 8:55
  • $\begingroup$ Yes. I was told to assume that. "In this Graph, the shortest path between any two vertices is on the MST. $\endgroup$ – Paddling Ghost Apr 12 '15 at 14:09
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.