# facts on tree and MST

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.

                False.


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

                True.


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

• 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. – Optidad Jan 6 at 8:14
• @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? – M K Jan 6 at 8:50
• 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. – Yuval Filmus Jan 6 at 9:11
• 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 ? – Optidad Jan 6 at 9:13
• @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. – 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).