Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

migrated from scicomp.stackexchange.com Nov 21 '12 at 15:53

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

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
why yes, but thank you –  AlanTuring Nov 24 '12 at 1:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.