spanning tree with exactly k colored edges

Question

I have a connected, undirected graph with edges that are each either black or white, and an integer k. I'm trying to write an algorithm that tells whether or not a spanning tree exists with exactly k black edges (doesn't necessarily have to find the actual tree).

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

But I'm having trouble wrapping my mind around whether there is necessarily a spanning tree for every k within that range. My intuition says yes, and it's worked for every example I've tried, but I can't figure out how to prove it.

Any advice? Thanks in advance.

How you find minimum and maximum number of black edges with Kruskal algorithm? — Saeed Amiri
Sorry, I think the nodes are black or white, you saying the edges. — Saeed Amiri

Keith Randall Keith Randall · Accepted Answer · 2010-12-06T07:57:33

Let G_min = spanning tree with the minimum # of black edges.

Let G_max = spanning tree with the maximum # of black edges.

Let k_min = # of black edges in G_min

Let k_max = # of black edges in G_max

The proof goes as follows. Set G = G_min. Repeat for every 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 there is at least one edge not in G_max in every cycle.

This algorithm maintains the spanning-tree-ness of G as it goes. It adds at most one black edge per step, so G demonstrates a spanning tree with k black edges for all k between k_min and k_max as it goes.

spanning tree with exactly k colored edges

2 Answers