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.

Given a simple1 undirected connected graph $G$ which has two kinds of edges, call them red edges and blue edges, I want to show that if it is possible to construct a spanning tree with exactly $\ell$ blue edges, and it is possible to construct a spanning tree with exactly $m$ blue edges, then for any $\ell\le k\le m$, it is possible to construct a spanning tree with exactly $k$ blue edges.

I don't think this is possible to show using a greedy algorithm / induction. As per the advice of a collaborator, I think you might be able to show this using some properties of cycles, but I'm not really sure where to go. That being said, bonus points will be awarded for any answer which can give a greedy algorithm / proof by induction.


1 - A graph with at most one edge between any unique pair of nodes, and no edge from any node to itself.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Order the edges of $G$ (in any way you like). Take your tree $A$ with $\ell$ blue edges, and add to it the first edge that is in the tree $B$ with $m$ blue edges but not in $A$. That creates a cycle, and that cycle must have at least one edge that's not in $B$; remove any such edge, and you have a new spanning tree, $A'$. Now repeat, using $A'$ and $B$. And repeat. And repeat. The end product is $B$. Along the way, you've created a list of spanning trees, each having at most one more or one fewer blue edge than the previous. So on the way you have visited every number from $\ell$ to $m$.

share|improve this answer
1  
I think you need a slight tweak here. If you order your edges such that when you add your first edge, it creates a cycle of all blue edges, you end up with an $A'$ that still has $\ell$ blue edges. However, I believe that you can always choose your edge to add such that it does not create an all blue cycle (assuming $\ell\neq m$), because if you can't, then you already have a spanning tree with the maximum number of blue edges, namely $m$ of them. Convoluted, but I think this covers it. –  brc Apr 17 '12 at 4:15
1  
I don't think your argument for ensuring only blue gets removed works because even in a non all blue cycle it is possible that the only non blue edges are from B. but the original answer works because we need not get A' with l+1 blue edges right away, we are merely guaranteed it eventually because the sequence of numbers describing the number of blue edges in the sequence of trees from A to B goes from l to m and always changes by 0 or +1. –  Wonder Apr 17 '12 at 4:23
    
@Wonder, quite right. –  Gerry Myerson Apr 17 '12 at 4:28

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.