Problem 1: Prove that rad(G) ≤ diam(G) ≤ 2 rad(G) for every graph G where rad(G) is the radius of graph G and diam(G) is the diameter of G.
Problem 2: Let G be a graph in which each edge e has a weight w(e) where w : E(G) →Z. Let T be a minimum weight spanning tree of G. Let P be the spanning tree produced by running Prim’s Algorithm on G. Prove that we can convert the optimal tree T into tree P by a sequence of edge replacements such that after each replacement, the graph resulting from the edge replacement is a tree with total weight no larger than T’s weight.
Problem 3: Let G be a directed graph in which each edge e has a weight w(e) as above. Prove that if some edge has a negative weight then Dijkstra’s Algorithm may fail to produce a single source shortest spanning tree.
Problem 4: Let G be a graph (directed or undirected) in which each edge e has a weight w(e) as above and let s be a vertex of G. Prove that there exists a spanning tree of T such that for each vertex v of G, dT(s,v) = dG(s,v). That is, the distance from s to v in T is equal to the shortest distance from s to v in G. Prove that this holds even if some edge weights are negative (but there is no negative weight cycle and no undirected edge with negative weight).
