[Solved]: MST with half the edges the maximum weight

Problem Detail: 

I have been cracking my head over the following question -

You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with repetitions), and the other half of edges all have weight C. Is it true that every MST of the graph includes the same number of edges of weight C?

If Yes, describe an efficient algorithm for finding the number of edges of weight C in every MST of the graph. The output is between 0 and |E| / 2, no need to return the MST.

If No, show a counterexample.

My work so far -

I've managed to prove to myself that the number of C weighing edges included in a spanning tree (not minimum) can be anywhere between 0 and |E| / 2 (using a cycle with C edges crossing it).

Obviously, I couldn't find a counterexample yet. It feels like what's preventing me from creating two different MST's with a different number of C edges is that for creating a graph that has more than one MST you need to have cycles, and if a C edge is contained in the cycle it won't be chosen (Kruskal). That is the direction I'm leaning towards for a proof, proving a more general claim obviously.

Assuming the above is in fact true, I need to show an efficient algorithm for finding the number of C edges in every MST. The question states there is no need to return an MST, so it seems like there should be a better algorithm than finding the MST and counting the number of C edges in it, meaning this algorithm should be more efficient than sorting. From what I showed above, it could be anywhere between 0 and |E| / 2 so I'm kinda lost here too.

Asked By : Ben Danon

Answered By : Hendrik Jan

All spanning trees have the same number of edges of each weight, as shown by Raphael as an answer to a question in that direction (thanks hengxin).

How to we count the number of heavy edges, of weight $C$, without computing the MST explicitly? First ignore the heavy edges. Also ignore the weights of the remaining edges. Determine the number $k$ of connected components in the resulting graph of light edges. The number of heavy edges then equals $k-1$. Here I assume all nodes in the graph are reachable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41169

 Ask a Question

 Download Related Notes/Documents