# Does cutting a minimum spanning tree generate two minimum Steiner tree?

I am trying to understand whether this intuition is true or false.

Given a minimum spanning tree (MST) of an undirected positive graph $$G=(V,E)$$.

Consider a MST $$T\subseteq G$$. Removing any single edge from $$T$$ would generate two separate Steiner trees with nodes partitioned in $$V_1,V_2$$. Are these minimal Steiner trees for the subsets of terminals $$V_1,V_2$$?

• Do you mean removing any single edge?
– prubin
Commented Apr 11, 2023 at 18:29
• No, just one, so to create 2 trees. There was a type. Thanks! Commented Apr 11, 2023 at 18:31

I'll equate a tree with a set of edges from $$E$$ and use the notation $$\ell(\hat{E})$$ to be the sum of the edge weights for any subset $$\hat{E} \subseteq E$$ of edges. A key observation is that in an undirected graph with positive edge weights, any minimum weight subgraph covering all vertices must be acyclic (else you could reduce weight by removing a cycle), so a MST is a minimum weight connected cover of the vertices.
Let $$T\subseteq E$$ be your MST, let $$\bar{e}$$ be the edge you delete, and let $$T_1$$ and $$T_2$$ be the resulting subtrees (so that $$T=T_{1}\dot{\cup}\left\{ \bar{e}\right\} \dot{\cup}T_{2}$$). Now suppose $$T_1$$ is not a Steiner tree for the terminals $$V_1.$$ That means there is a set of nodes $$\hat{V}\subseteq V_2$$ from the other subtree that you can "borrow" to produce a tree $$\hat{T}$$ connecting all the nodes in $$V_1\dot{\cup}\hat{V}$$ such that $$\ell(\hat{T}) < \ell(T_1).$$ In that case, the set of edges $$E^* = \hat{T} \cup T_2$$ produces a connected graph (not necessarily a tree) covering all of $$V$$ (because all nodes in $$V_1$$ are connected by $$\hat{T},$$ all nodes in $$V_2$$ are connected by $$T_2,$$ and at least one node in $$V_1$$ is connected to at least one node in $$\hat{V} \subseteq V_2$$ via $$\hat{T}$$). The sum of the edge weights in $$E^*$$ is $$\ell(E^*) = \ell(\hat{T}) + \ell(\hat{T_2}) < \ell(T_1) + \ell(T_2) = \ell(T),$$ contradicting $$T$$ being a MST.