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

New contributor
Rab is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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 at 12:03

1 Answer 1

0
$\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\}$. Note $V'$ the vertices covered by $E$: $V' = \{v\in V\mid \exists e\in E\text{ such that } v\in e\}$.

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

Rab is a new contributor. Be nice, and check out our Code of Conduct.

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.