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

Question

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$?

Answer 1

I think the answer is yes, but I recommend triple-checking my logic. I assume by "positive graph" you mean positive edge weights.

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.