# Sub-Graph of a Minimum Spanning tree

I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question.

Currently my thinking leads me to believe that since we already have a minimum spanning tree G therefore since we have sub-nodes present in that minimum spanning tree, a G' has to exist. As far as the condition goes, i'm at a bit of a loss.

A graph X′ is a sub-graph of graph X if the node and edge sets of X′ are subsets of the node and edge sets of X respectively. Let us have (V,T) as a minimum spanning tree of G and G′=(V′,E′) be a connected sub-graph of G.

(a) Prove that (V′,E′∩T) is a sub-graph of a minimum spanning tree of G′.

(b) Under what condition is (V′,E′∩T) a minimum spanning tree of G′? Prove your claim.

-

## migrated from scicomp.stackexchange.comNov 21 '12 at 15:53

This question came from our site for scientists using computers to solve scientific problems.

Now $(V',E'\cap T)$ clearly has no cycles, so it can be extended to a spanning tree of $G'$, perhaps in many ways. Among those ways, pick one, call it $T^+$ of minimal weight: we want to show $T^+$ is a minimum weight spanning tree for $G'$.
Well, suppose it isn't. Then there's a different tree, $T^-$, that is a spanning tree for $G'$ and has smaller weight than $T^+$. Now prove that you can extend $T^-$ to be a spanning tree $T^*$ for $G$ by adding some of the edges of $T$ (this, I think, is where you're going to have to add some details to fill out this sketch). But then $T^*$ has weight less than that of $T$, contradiction.
For (b), since we have proved $(V',E'\cap T)$ is a subgraph of a minimum spanning tree of $G'$, it follows that it is a minimum spanning tree of $G'$ if and only if it is a spanning tree of $G'$.