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