Hi, let's consider this problem.
If you have a connected graph with edges colored red or blue, to find out whether you can construct the spanning tree with exactly $$$K$$$ number of blue edges then — find the minimum number of blue edges that can be used, also find the maximum. If $$$K$$$ is in $$$[min, max]$$$ then it's possible, otherwise, no.
What is the proof of it?
I was thinking like this — If it is possible to construct the tree with $$$A$$$ vertices, and also with $$$A + 2$$$ vertices, then $$$A + 1$$$ is also possible, but why, how? Can we probably relate the solution with $$$A$$$ vertices to $$$A + 2$$$ vertices?
Thanks.
I'll assume that the graph $$$G$$$ is simple.
Think about it in terms of forests that are made when you take vertices of the same color.
Note that for the minimum number of blue edges, you need to maximize the number of red edges. If you take the subgraph $$$G_{red}$$$ that doesn't have any blue edges, any spanning tree can have at most $$$|V| - \text{number of components of } G_{red}$$$ red edges, and no more, i.e., it must have no less than $$$\text{number of components of } G_{red} - 1$$$ blue edges. Similarly, the maximum number of blue edges you can have in a spanning tree is $$$|V| - \text{number of components of }G_{blue}$$$.
Now let's start from a spanning tree that has $$$\text{number of components of } G_{red} - 1$$$ blue edges. Suppose we haven't reached the maximum number of blue edges yet. Now we claim that there is at least one blue edge that we haven't added to the spanning tree yet, which is in a cycle that also contains a red edge.
Suppose that this isn't the case. Remove all red edges from the current spanning tree. The fact that we can't add a blue edge to this forest to reduce the number of components implies that this is indeed the least number of components we can get with blue edges, which means that this is precisely the case when we have already added the maximum number of blue edges we could, which is a contradiction.
So we have shown that we can always find a blue edge, which on adding to this spanning tree, gives us a cycle which has a red edge in it. Now, we can just remove the red edge from this graph to give us back a tree. This tree has the property that it has exactly one more blue edge compared to the previous tree, so we are done.