Enclosing tree with exactly k colored edges

Question

I have a connected, undirected graph with edges, each of which is either black or white, and an integer k. I am trying to write an algorithm that says if a spanning tree exists with exactly k black edges (it is not necessary to find the actual tree).

I used the Kruskal algorithm to find the minimum and maximum possible number of black edges in the spanning tree. If k is outside this range, a spanning tree with k edges cannot exist.

But I am having trouble getting around my question of whether a spanning tree necessarily exists for every k in this range. My intuition says yes, and it worked for every example I tried, but I cannot figure out how to prove it.

Any tips? Thanks in advance.

Answer 1

Let G_min = a spanning tree with minimal # black edges.

Let G_max = spanning tree with maximal # black edges.

Let k_min = # black edges in G_min

Let k_max = # black edges in G_max

Evidence. Set G = G_min. Repeat for each black edge in G_max:

  1) If the edge is already in G, do nothing.
  2) If the edge is not in G, add it to G and remove another edge
     from the cycle thus induced in G.  Remove one not in G_max.

Step 2 is always possible, because at least one edge is not in G_max in each cycle.

This algorithm supports the spanning tree G when it goes. He adds no more than one black edge per step, so G shows a spanning tree with k black edges for all k between k_min and k_max as it passes.

Answer 2

- , Gmin, . gmin = case, 1, 0. , , . gmin.