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.

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.

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 |V| - 1 non-cyclic edges that are each 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.

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.

I am trying to prove the algorithm for Question 5 in this practice exam: https://www.cs.cmu.edu/afs/cs/academic/class/15210-f15/www/exams/exam2-practice-sol.pdf.

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

Claim 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'.

Claim 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.

Claim 3: The algorithm given will generate a set of |V| - 1 non-cyclic edges that are each light for at least one cut; thus, it will generate a minimum spanning tree.

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.

Thank you.

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 |V| - 1 non-cyclic edges that are each light for at least one cut; thus, it will generate a minimum spanning tree.

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.