Minimum spanning tree and its connected subgraph

Problem Detail: 

This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:

• The accepted answer at [2] is still in dispute.
• The proof given by @eh9 is based on Kruskal's algorithm.
• I am seeking for a proof independent of any MST algorithms.

---

Problem: Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T \cap H$ is contained in some MST of $H$.

---

My partial trial is by contradiction:

Suppose that $T \cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST_{H}$), there exists an edge $e$ such that $e \in T \cap H$, and however, $e \notin MST_{H}$.
Now we can add $e$ to $MST_{H}$ to get $MST_{H} + {e}$ which contains a cycle (denoted $C$).

• Because $MST_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST_{H}$, we have that every other edge $e'$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $\forall e' \in C, e' \neq e. w(e') \le w(e)$).
• There exists at lease one edge (denoted $e''$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.

Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$

I failed to continue...

---

1. Algorithms, Chapter 5: Greedy algorithms
2. "Minimum Spanning tree subgraph"@StackOverflow

Asked By : hengxin

Answered By : Mahmoud A.

If we construct a spanning tree for $H$ containing $T_G \cap H$ then your approach leads to a trivial contradiction (meaning that your initial assumption is automatically contradicted by any direct proof). Here is the construction of a MST for $H$ from a MST for $G$:

Let $MST_\Psi$ be the set of minimum spanning trees for the graph $\Psi$. The spanning tree $T_\Psi$ is not minimum for $\Psi$ if there is another spanning tree for $\Psi$ with smaller weight. Start with $T_H \in MST_H, T_G \in MST_G$.

While there is an edge $e \in T_G \cap H$ such that $e \not\in T_H$ do:

1- Find $e$ and add it to $T_H$ to create a cycle. For every other edge $e' \not\in T_G$ in the cycle we have $w(e') = w(e)$ (because if $w(e)>w(e')$ then replacing $e$ with $e'$ in $T_G$ gives a better ST for $G$, thereby $T_G$ is not minimum for $G$. If $w(e)<w(e')$ then since $e \not\in T_H$ we can replace $e'$ with $e$ in $T_H$ to obtain a better spanning tree for $H$ contradicting $T_H$ being MST for $H$). Let $e'' \not\in T_G$ be one of these edges. We can safely replace $e''$ with $e$ in order to obtain $T'_H = T_H \setminus \{e''\} \cup \{e\} \in MST_H$.

2- Rename $T'_H$ to $T_H$.

EndWhile

After the loop we have $T_G \cap H \subseteq T_H$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18867