Graph Theory - Minimum Spanning Tree (MST) Question

Question

Let $ = (,)$ be an undirected connected weighted graph.

For a spanning tree $$ of $$, let ($$) be the maximum weight of an edge in $$.

An economic tree of a graph $$ is a spanning tree of $$ with a minimal possible .

True/False: If $$ is a MST of $$, then $$ is an economic tree of $$.

---

I assume that this one is true.

I want to assume towards a contradiction that $T$ is a MST that is not an economic tree, and try to get a contradiction that T can't be a MST anymore.

I struggle to prove it, I will appreciate some hints!

Thanks a lot!

Answer 1

Wrong Answer left for the record.

Unless I am interpreting your definitions incorrectly, this is false.

Consider $C_4$, with edge weights $1,1,1,2$. Then any three adjacent edges comprise a minimal spanning tree, but three of the four minimal spanning trees are not economic.

Answer 2

You are right, any MST is an economic tree.

You can prove that the maximum cost of an edge in an MST is equal to the minimum cost $c$ such that the graph restricted to edges of weight at most $c$ is connected.

This will imply your proposition.

More details. Let $w : E \to \mathbb{N}$ be the weight function. For $t \in \mathbb{N}$, let $G_t = (V,\{e \in E : w(e) \leq t\}$, and let $t_0$ be minimum such that $G_{t_0}$ is connected. Also let $T \subseteq E$ be a minimum cost spanning tree, and $w_T = \max_{e \in T} w(e)$. We want to prove $w_t = t_0$.

To prove that $w_T \geq t_0$, you just have to prove that $G_{w_T}$ is connected, which should be easy, then it follows by the choice of $t_0$.

To prove that $w_T \leq t_0$, we need this proposition:

Proposition: for any minimum spanning tree $T \subseteq E$ and any $e \in T$, there is a cut $\delta(X)$ in $G$ such that $e \in \delta(X)$ and $w(e) = \min_{e' \in \delta(X)} w(e')$.

You can choose for $X$ one of the two connected component of $T \setminus e$.