So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red edges or says non exists otherwise.
so what we have done so far is:
Let every red edge have weight of $-1$ and every blue edge have weight of $0$
use an algorithm that finds a minimum spanning tree in linear time. so we have a spanning tree $T$ that its weight is minimal, meaning we used as much red edges as we can because red edges will only decrease the weight.
if there are less than $K$ red edges in $T$, we return that it is impossible to find one.
now if there are exactly $K$ red edges we are done.
IF there are more than $K$ red edges we need to replace them with blue ones.
and here is our problem, how do we do that in linear time?
every blue edge added will indeed create a cycle. so removing one red edge from the cycle will work but how can we ensue linearity in this way?.. is this even a good approach? any leads will be appreciated!