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.


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$ Commented Jul 30, 2018 at 9:11
  • $\begingroup$ You're welcome :) Not sure if you missed the second part of my comment though, or disagree with it? $\endgroup$ Commented Jul 30, 2018 at 18:02
  • 1
    $\begingroup$ "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) $\endgroup$ Commented Jul 30, 2018 at 20:05
  • $\begingroup$ @j_random_hacker, thanks for pointing out three typos. I have fixed them. $\endgroup$
    – John L.
    Commented Jul 30, 2018 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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