# CS515 Homework 8

CS515, Fall 2020

Homework 8

Due: November 11, 2020

1. (16 pts.) Let e1 and e2 be two lowest-weight edges in a connected and weighted graph G. Show that

e1 and e2 belong to some MST in G.

2. (16 pts.) Consider this statement: If e1, e2 and e3 are three lowest-weighted edges in a connected

and weighted graph G, then e1, e2 and e3 belong to some MST in G. Is this statement true? Either

prove it or show a counterexample.

3. (16 pts.) Show that every MST in a connected, weighted graph G is returned by Kruskal’s algorithm

for some sorted order of the edges of G.

4. (16 pts.) Let G be a connected, weighted graph G and let e be an edge in G. Is it possible for e to

be a part of every MST in G? If so, describe a general condition that guarantees it.

5. (20 pts.) Let G be a connected, weighted graph G and let e be a highest-weight edge in G. Is it

possible for e to be a part of some MST in G? If you think the answer is no, explain why. If you

think the answer is yes, formulate a possibly general conditions under which e is included in some

MST.

6. (16 pts.) Suppose all edge weights in a graph are integers in the range 1 to V . How fast can you

make Kruskal’s algorithm run? Explain.

7. (Bonus: 30 pts.) A directed graph G = (V; E) is semi-connected if for all pairs of vertices u; v 2 V ,

u is reachable from v or v is reachable from u. Describe a O(jV j + jEj) algorithm to determine

whether or not G is semi-connected. A precise narrative is acceptable. Explain why your algorithm

is correct and justify the running time.