[Solved]: How to draw a graph to disprove this statement?

Problem Detail: 

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.

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.

Asked By : committedandroider

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents