MST with half the edges the maximum weight 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.
If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$.  If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer.

So now you want to know whether the answer is yes.  To see that it is, observe that each MST is constructed by running the greedy algorithm on a specific linear extension of the partial order induced by the weights.  In your case, the edges $E$ partitioned into sets $E_{&lt;C}$ and $E_C$, and every edge in $E_{&lt;C}$ comes before any edge in $E_C$ for all of these linear extensions.  That tells you that every MST is made of a spanning forest $F$ on the subgraph induced by $E_{&lt;C}$ and some edges from $E_C$; since all the choices for $F$ have the same size, we are done.