1
$\begingroup$

The Problem: Indicate whether the following statements are true or false:

  • a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
  • b. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph
  • c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree
  • d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree

I read from Min Edge that every MST must contain the minimum weighted edge and from Partial Solutions that two of the assertions are true while the rest of the two are false.

From those two statements, I concluded that the first two statements(a, b) are true while the last two statements(c,d) are false.

Here is the diagram I used to illustrate that the last option, d, is false.

enter image description here

The edge weights are not distinct(two twos) and there is only one minimum spanning tree.

Can anyone give a counterexample graph to choice option c? I tried some examples(too many to include in here) but each time with distinct weights, using Prim's algorithm, I only found one MST.

$\endgroup$
  • 1
    $\begingroup$ It seems to me you can just remove the parts a, b, and d from your question since you already have an answer for them. Including them makes your question unnecessarily long. Also, you already claim c is false as well. Why is that? Why do you doubt your answer? What is your question? $\endgroup$ – Juho Jun 6 '15 at 20:48
  • $\begingroup$ @Juho . C is false because the solutions said that two of the following are true. The two of the following are a and b. I need parts a and b to add context to this question. I am trying to show a counterexample to c. My question is how would you find a counterexample to c? The reader would need to read the question(and thus options a,b) to understand why I am trying to show c is false $\endgroup$ – committedandroider Jun 6 '15 at 20:55
3
$\begingroup$

You have made a mistake interpreting the wording of the question compared to the Stackoverflow question (link in case of later editing).

Notice that in options (a) and (b), the phrasing is a minimum weight edge, whereas in the Stackoverflow question the phrasing is the minimum weight edge. In your question, there's no guarantee that the edge is the only edge with that weight, in the Stackoverflow question, there is exactly one edge with the lowest weight.

Thus the mistake is assuming that (b) is true, when in fact it is false. The two true options are (a) and (c), which is why you can't find a counter example to (c).

In both (a) and (c) however, the proof is very similar to that in the Stackoverflow question. In fact (c) is given by applying that proof inductively. (a) is given by basically the same argument, but you show that the tree made by adding the given edge and removing some other edge from the cycle can't have higher weight (because the new edge has minimum weight).

To see that (b) is false, just take the graph $K_{n}$ where all edge weights are the same. Any spanning tree is a minimum spanning tree.

For (d), consider the following graph; take a tree on $n$ vertices, give all these edges weight $1$. Then add all non-edges, give these new edges weight $2$. Clearly there's only one MST, but there's $\binom{n}{2} - n + 1$ edges with the same weight.

$\endgroup$
  • $\begingroup$ Is my counterexample proof for d sufficient as well? $\endgroup$ – committedandroider Jun 7 '15 at 3:59
  • 1
    $\begingroup$ @committedandroider, yes (I got overexcited writing the answer and forgot that you'd already solved that one). $\endgroup$ – Luke Mathieson Jun 7 '15 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.