- 1

- 0

**1. 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.

**2. Homework Equations**

**3. The Attempt at a Solution**