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