2
$\begingroup$

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))$.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – Rab
    Sep 21, 2022 at 12:03

1 Answer 1

1
$\begingroup$

The property you speak of is indeed true.

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.