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:

1) if this means that for any pair of vertices and for any shortest path between them, it lies on MST So this statement is False. for example Let's assume that we have a graph with two vertices $\{1, 2\}$ and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex ($[1, 2]$, $[1, 2, 1, 2]$, ...)

2) if this means For each $a,b\in V$, for each shortest path $P$ from $a$ to $b$ in $G$ there exists a minimum spanning tree $T$ of $G$ such that $p$ is contained in $T$. this statement is True.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top