# 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. Jan 6, 2021 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, 2021 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. Jan 6, 2021 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 ? Jan 6, 2021 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. Jan 6, 2021 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).

• would you please give me a simple example?
– M K
Jan 6, 2021 at 23:17
• 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.
– timg
Jan 6, 2021 at 23:18
• !! what about fact II and edge weights and MST and ...
– M K
Jan 6, 2021 at 23:19
• 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.
– timg
Jan 6, 2021 at 23:21