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
  • $\begingroup$ This seems to have bubble back. What do you mean by proofs based on greedy algorithms are not proofs? (Also, my answer below seems to be correct, but it is down voted.) $\endgroup$
    – Louis
    Jun 2, 2015 at 10:21
  • $\begingroup$ @Louis It is just a subjective view. I prefer to proofs which are not based on concrete MST algorithms. I changed the wording. $\endgroup$
    – hengxin
    Jun 2, 2015 at 10:30
  • $\begingroup$ You can convert them mechanically, if the algorithm is Kruskal's. $\endgroup$
    – Louis
    Jun 2, 2015 at 10:31

3 Answers 3


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


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

  • 1
    $\begingroup$ @D.W. When I re-read this answer today, I find there are flaws in it. Consider the figures for an example: in figure (5), the edge CD in the cycle created by adding edge CE is not in $T_G$ in figure (2), but we have $w(CD) > w(CE)$. So the claim For every other edge e′∉TG in the cycle we have w(e′)=w(e) does not hold. $\endgroup$
    – hengxin
    Jun 1, 2015 at 12:46

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: mst-subgraph

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$


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

  • 1
    $\begingroup$ thanks a lot for this correction. As you showed, the flaw was that the equality $w(e)=w(e')$ holds for SOME edge $e' \notin T_G$ in the cycle, but not for EVERY... $\endgroup$
    – Parham
    Feb 26, 2016 at 14:17
  • $\begingroup$ What is C? <unnecessary characters to satisfy min char limit> $\endgroup$ Dec 16, 2018 at 5:22

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.

  • $\begingroup$ @Louis, you've misunderstood the problem. The problem is not to show that the MST of $H$ extends to a MST of $G$. The problem is to show that $T \cap H$ is contained in some MST of $H$, which is different. For instance, if $T \cap H$ is the empty set, then it is certainly contained in some MST of $H$. For this reason, your alleged counterexample in your comment is not in fact a counterexample to the claim we need to prove. In your example, $T \cap H$ is the empty set. The MST of $H$ is $\{(2,3)\}$ (a tree containing just the edge $23$). The empty set is contained in $\{(2,3)\}$. $\endgroup$
    – D.W.
    Dec 11, 2013 at 21:35
  • $\begingroup$ @D.W.: This is old so I don't remember, but what is there doesn't go with your comment any more. $\endgroup$
    – Louis
    Jun 2, 2015 at 10:22
  • $\begingroup$ I don't understand the contradiction well. You claim that $F$ is a sub-tree of $T$. Does $F$ only contain such $e'$ edges? Could you please illustrate it in a picture, if possible? $\endgroup$
    – hengxin
    Jun 2, 2015 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.