I am trying to prove the algorithm for Question 5 in this practice exam.

I am trying to prove this algorithm with the following three claims:

  1. Suppose we have a graph G, a minimum spanning tree T, and a set of edges A that is a subset of T. Suppose that we also have a cut C = (S, V - S) that respects A, and edge e = (u, v) is a light edge for that cut. Then, A $\cup$ { e } is also a subset of some minimum spanning tree T'.

  2. Suppose we have a graph G with |V| vertices that has a minimum spanning tree. Suppose we also have a set of |V| - 1 edges = <$e_1$, $e_2$, ..., $e_n$>, such that each edge is a light edge for some cut C, and these edges do not form a cycle. This set of edges must form a minimum spanning tree.

  3. The algorithm given will generate a set of acyclic |V| - 1 edges each of which is light for at least one cut; thus, it will generate a minimum spanning tree.

The first and third claims are easy to prove, but I am unable to prove the second claim. This is what I have so far:

Trivially, the set of edges must form a spanning tree - it is not possible to have |V| - 1 edges and no cycles without connecting all |V| vertices.

This spanning tree must also be a minimum spanning tree: suppose we have a new empty set of edges A. A is trivially a subset of some minimum spanning tree for G. A $\cup$ { $e_1$ } is also a subset of some MST by Claim 1 (because $e_1$ is a light edge for cut C which trivially respects the empty set A).

Now let us examine edge an edge $e_2 = (u, v)$ that is incident to one vertex touched by $e_1$. We can assume without loss of generality that there is currently no edge incident to $v$. [I can't prove that $e_2$ is safe to add].

I was wondering if this claim is even correct - and if so, how I can go about proving it.

up vote 3 down vote accepted

The answer to the question in the title, "Is a set of acyclic $|V|-1$ light edges always a Minimum Spanning Tree?" is no. That is, the second claim in the question is not true. Hence, the third claim is not true, either.

Here is a simple counterexample. Let $H$ be a graph the complete graph with 4 vertices, $\{a,b, c,d\}$ and weights, $ab\rightarrow 1$, $cd\rightarrow 1$, $ac\rightarrow 2$, $ad\rightarrow 2$, $bc\rightarrow 2$, $bd\rightarrow 2$. The weight of a minimum spanning tree $\{ab, ac, cd\}$ is $1+1+2=4$. Consider the spanning tree made by the 3 edges, $\{ac, bc, bd\}$, each of which is light for the cut $\{a, b\}, \{c,d\}$. However, the weight of this spanning tree is $2 + 2 + 2 = 6$, which is greater than $4$.

One might be wondering why it might be so hard to come up with a counterexample. Part of the reason might be that if the weights of edges of $G$ are different, then $G$ has only one minimum spanning tree, which includes all light edges for every cut.

  • I think you meant to include $cd$ instead of $ad$ to get a weight-4 tree, and I would also call it a minimum spanning tree. – j_random_hacker Jul 30 at 9:11
  • You're welcome :) Not sure if you missed the second part of my comment though, or disagree with it? – j_random_hacker Jul 30 at 18:02
  • 1
    "minimal spanning tree" is still there in paragraph 2. I think it's confusing -- I immediately thought "What does 'minimal' mean? It must be something different from 'minimum', otherwise s/he would have just written the latter -- but what? TTBOMK it's not a standard term, the author doesn't define it, and I can't even imagine a sense in which a spanning tree could be minimal without simultaneously also being minimum, so I'm not sure what the point of the new term could be..." (Cf. the important distinction between a minimum matching and a minimal matching) – j_random_hacker Jul 30 at 20:05
  • @j_random_hacker, thanks for pointing out three typos. I have fixed them. – Apass.Jack Jul 30 at 23:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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