title: Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time
body: <p>Given a graph <strong>G</strong> with red and blue edges and a constant <em>K</em>, devise a deterministic, linear time algorithm that finds a spanning tree of <strong>G</strong> with exactly <em>K</em> red edges (or returns <code>False</code> if such a spanning tree does not exist).</p>
  
  <p>What we have done so far:</p>
  
  <p>Let every red edge have weight of -1 and every blue edge have weight of 0.</p>
  
  <p>Find a minimum spanning tree (using a standard linear time algorithm). So, we have a spanning tree <strong>T</strong> with minimal weight, meaning we used as many red edges as we can because red edges will only decrease the weight.</p>
  
  <p>If there are less than <em>K</em> red edges in <strong>T</strong>, we return <code>False</code>.</p>
  
  <p>If there are exactly <em>K</em> red edges, we are done, <strong>T</strong> is the answer.</p>
  
  <p>If there are more than <em>K</em> red edges, we need to replace them with blue ones.</p>
  
  <p>This is our problem, how do we do that in linear time?</p>
  
  <p>Every blue edge added will 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?</p>