Minimum Spanning tree subgraph

Question

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!

Answer 1

for (a)

I don't really get the question ... can you explain ?

for (b)

I think it's if

for every e=(u,v) in T if u in V' and v in V' then e in E

then we have (V′,E′∩T) is a minimum spanning tree of G'.

Coz :

1. If some e that has e=(u,v) in T if u in V' and v in V' but not in E', then (V′,E′∩T) is not connected at all. It certainly can't be a spanning tree of G'
2. If the condition stands, but (V′,E′∩T) is not a spanning tree of G', then G' has a spanning tree with less cost, let's say it's Tg. We can construct a spanning tree T' of G with less cost than T, by: (i) remove every e=(u,v) , u in V' and v in V' and e in T from T (ii) add every e=(u,v) , u in V' and v in V' and e in Tg . The resulting graph is a spanning tree of G (because it's connected while having the same number of edges of T) and has less cost than T. So it can never happen since we already know T is a minimul spanning tree of T.