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!