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.
thanks in advance!
Best Answer
I suppose it's a little bit late to help you for your test, but here goes.
First, when you write "minimum spanning tree," all spanning trees in a given graph have the same number of nodes and the same number of edges. So I'm going to assume that what we are dealing with is a weighted graph, and we are discussing minimal weight spanning trees.
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'$.