Minimum spanning tree and its connected subgraph

Question

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

Answer 1

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

Answer 2

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.

Consider the figures for an example:

In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)<w(e=CE)$. So the claim "For every other edge $e' \notin T_G$ in the cycle we have $w(e′)=w(e)$" does not hold.

Note: In the following, I fix the flaws. I leave the answer given by @Mahmoud A. as accepted because it is original and insightful.

Correction: While where is an edge $e \in T_G \cap H$ such that $e \notin T_H$ do:

1. Adding $e$ to $T_H$ to create a cycle $C$.

   • 1.1 Because $T_H$ is an MST of $H$, for every other edge $e' \in C$ we have $w(e') \le w(e)$. Otherwise, for any edge $e' \in C$ such that $w(e')>w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.

   • 1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
     We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'') < w(e)$, then $T_{G} - \{ e \} + \{ e'' \}$ has smaller weight than $T_G$.

   • 1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
     Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.

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

EndWhile

After the loop we have $T_{G} \cap H \subseteq T_H$.

Answer 3

First assume the edge weights are distinct. Kruskal's algorithm then implies that the MSTs $T$ of $G$ and $T'$ of $H$ are unique. Let $S = T\cap E(H)$ and suppose that $e\in S\setminus T'$. Because $e\notin T'$, the weight $w(e) > w(e')$ for each $e'$ on the fundamental cycle $C$ of $e$ in $T'$. This then implies that, at the moment $e$ was added to $T$ in the Kruskal algorithm, each such $e'$ already was spanned by some connected component of a sub-forest $F$ of $T$.

In fact, $F$ has to be a sub-tree of $T$, since $C\setminus e$ is connected, and the trees of $F$ covering the endpoints of pairs of edges incident on a common vertex must be the same.

Now we are at a contradiction: both endpoints of $e$ are in a subtree of $T$ not containing $e$. This is impossible if $T$ is actually a tree.

For the non-unique weights case, just pick an order of the edges consistent with the weights and then perturb them to reduce to the distinct case.