(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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. Relevant equations

3. The attempt at a solution

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Hi need help with algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**