CSDS 455: Applied Graph Theory
Homework 6
Next week we will be looking at distances in a graph. For this homework, you will need to look up distance
parameters for graphs, and to read about Kruskal’s and Prim’s algorithms for minimum weight spanning
trees and Dijkstra’s algorithm for finding a single source shortest paths tree.
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).
