# Does exist a tree where the inequality with MST edges are strict?

We know that if $$T_1 = \{e_1, \dots, e_n\}$$ and $$T_2=\{f_1, \dots, f_n\}$$ are MST then if we order the edges such as $$w(e_1) \le w(e_2) \le \dots \le w(e_n)$$ $$w(f_1) \le w(f_2) \le \dots \le w(f_n)$$

then $$w(e_i)=w(f_i)$$ for all $$i\in [n]$$

This also (trivially) implies that $$w(e_1) \le w(f_i)$$ for all $$i\in [n]$$

Does this equality also holds when $$T_2$$ is a spanning tree but not minimal? I have been trying to prove it for a while and are not succeeding.

Assume that it is not and let $$k$$ be the first index where $$w(f_i) < w(e_i)$$ and denote $$f=(u,v)$$. Let us look at the unique path connecting $$f=(u,v)$$ in $$T_1$$ if that path contains any of the $$\{e_{k}, \dots, e_n\}$$ edges then we can replace that edge with $$f_i$$ and we get that $$T_1$$ is not a MST, otherwise that path contains at-least one of the edges $$\{e_1, \dots, e_k\}$$.

There is where I am stuck, I am trying to say that $$\{f_1, \dots, f_{k}\}$$ must contain an edge that is safe to add to $$T_1$$, my idea is that one of the edges in $$\{f_1, \dots, f_{k}\}$$ must close a loop in the edges $$e_{k}, \dots, e_n$$ and therefore it is safe to replace it but I can't get it to work.

Appreciate any help.

This also proves that MSTs are invariant under increasing functions (that is, if $$f(x)$$ is an increasing function that an MST w.r.t $$w(E)$$ would remain an MST w.r.t $$f(w(E))$$.

• Yes, I assume that $T_2$ is still a spanning tree (I tried the approach where I assume that none of the $f_i$ close a loop and show a contradiction; that is $T_2$ is not spanning but also failed)
– Rab
Sep 21, 2022 at 12:03

Denote $$E = \{e_1, e_2, …, e_{k-1}\}$$ and $$F = \{f_1, f_2, …, f_k\}$$.
I will prove that there exists $$f\in F\setminus E$$ such that $$(V, E\cup\{f\})$$ is acyclic. That would mean that $$w(e_k) \leqslant w(f) \leqslant w(f_k)$$.
Suppose that $$(V, E\cup\{f\})$$ contains a cycle for each $$f\in F$$.
Denote $$C_1, …, C_m$$ the connected components of $$(V, E)$$. Since $$(V, E\cup \{f\})$$ contains a cycle for all $$f\in F$$, that means that each $$f$$ is an edge between two vertices of a certain $$C_i$$. If we define $$E_i = \{e\in E\mid e \text{ is an edge between two vertices of }C_i\}$$ and $$F_i = \{f\in F\mid f \text{ is an edge between two vertices of }C_i\}$$, the pigeonhole principle says that there exists $$i\in \{1, …, m\}$$ such that $$|F_i| > |E_i|$$. But since $$(C_i, E_i)$$ is a tree, that means that $$|E_i| = |C_i| - 1$$. That implies that $$(C_i, F_i)$$ contains a cycle, and that $$T_2$$ contains a cycle.
We conclude by contradiction that $$w(e_k) \leqslant w(f_k)$$.