We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.

The following Facts is False, and True.

$I$) Graph $G$ is a Tree.


$II$) weight of each ${u,v}$ edge, is at least equal to heaviest edge in shortest path from $u$ to $v$.


Anyone can describe me why the second fact is hold? Intuitive idea or example or proof?

  • 2
    $\begingroup$ If I undestand well the second statement, it is true for any graph (with non negative weights). Just forgot the initial assumptions and try to build a simple graph where II) is False, you will quickly figure why it's impossible. $\endgroup$ – Optidad Jan 6 at 8:14
  • $\begingroup$ @Optidad maybe this is very basic question. but I need an example why this is true? it's very easy for experts. would you please show me an example at least I get concept? $\endgroup$ – M K Jan 6 at 8:50
  • $\begingroup$ I'm not sure what the phrase "shortest path between any two vertices on the graph is on MST". There could be several shortest paths and several MSTs. $\endgroup$ – Yuval Filmus Jan 6 at 9:11
  • $\begingroup$ Let's take a complete graph with 3 vertices $a$, $b$, $c$. The edges weights are $w_{ab}$, $w_{ac}$, $w_{bc}$. Let's consider statement II on the path from $a$ to $b$. If the shortest path is $a \Rightarrow b$, the statement is checked of course, but what if the shortest path is $a \Rightarrow c \Rightarrow b$ ? What relation can you write between the 3 weights ? $\endgroup$ – Optidad Jan 6 at 9:13
  • $\begingroup$ @Yuval_Filmus Does the "all distinct weights" statement let the possibility to have several MST ? I believe that based on Kruskal algorithm, we can show that it is unique. $\endgroup$ – Optidad Jan 6 at 9:20

Assumption $II$ is true for any general graph with non-negative edge weights, including the graph $G$ with specific properties. To understand this, think about the inverse of the statement.

Let's assume the weight a $u,v$ edge is lighter than edge $e$ on the shortest path. The shortest path is made out of $e$ + $C$ where $C$ is some constant. Because $C >= 0$(non-negative graph) and $e$ < edge between $u,v$, by definition the shortest path we have assumed to be optimal is not(because the edge directly connecting $u$ to $v$ would be shorter).

To your specific graph into this, this lighter edge from $u,v$ cannot exist because if it did, it would have to be part of the minimum spanning tree(and thus part of the shortest path as mentioned in your description).

  • $\begingroup$ would you please give me a simple example? $\endgroup$ – M K Jan 6 at 23:17
  • $\begingroup$ Graph G has nodes A, B, C. A and B are connected by 10. B and C and connected by 1. If this is the shortest, it is not possible for A and C to be connected with an edge < 10, because then the BC edge and AC edge will be used. $\endgroup$ – timg Jan 6 at 23:18
  • $\begingroup$ !! what about fact II and edge weights and MST and ... $\endgroup$ – M K Jan 6 at 23:19
  • $\begingroup$ This problem has more to do with general graphs rather than just your graph, but in my example that would mean that AB would not be part of the MST thus not part of the shortest path. $\endgroup$ – timg Jan 6 at 23:21

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.