Solving Connected Graphs with Algorithm: K Blue/Red Edges

[frank_buf@yahoo]

Homework Statement

Given a connected graph G = (V,E). Let n = |V |. Each edge in G is already colored
with either RED or BLUE. Devise an efficient (i.e. polynomial-time) algorithm which, given an integer k,
1 <= k <= n − 1, either (a) returns a spanning tree with k BLUE edges and n − 1 − k RED edges, or (b)
reports correctly that no such tree exists.

Homework Equations

The Attempt at a Solution

 

[berkeman]

Welcome to the PF, Frank. You need to show us all of your work and thoughts on this problem before we can help you. Why did you not fill in #2 and #2 in our Homework Posting Template? What are the relevant concepts that we should use in trying to help you figure out how to solve this question?