5
$\begingroup$

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
$\endgroup$
  • $\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 '15 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 '15 at 10:30
  • $\begingroup$ You can convert them mechanically, if the algorithm is Kruskal's. $\endgroup$ – Louis Jun 2 '15 at 10:31
4
$\begingroup$

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

$\endgroup$
  • 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 '15 at 12:46
7
$\begingroup$

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$

EndWhile

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

$\endgroup$
  • 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 '16 at 14:17
  • $\begingroup$ What is C? <unnecessary characters to satisfy min char limit> $\endgroup$ – Abhijit Sarkar Dec 16 '18 at 5:22
-1
$\begingroup$

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.

$\endgroup$
  • $\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 '13 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 '15 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 '15 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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