# Showing existence of a spanning tree in a graph with two kinds of edges using $k$ of one kind of edge

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.

-

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