CSDS 455: Applied Graph Theory
Homework 7
Problem 1: Prove that the graph obtained from Kn by deleting one edge has (n − 2)n
n−3
spanning trees.
Problem 2: Let G be a connected graph in which each edge has a positive weight/length. Recall that
Dijkstra’s algorithm takes a vertex s of G and creates a shortest path spanning tree T from s. If T is a
shortest path spanning tree from s, then dT (s, v) = dG(s, v) for all v ∈ V (G).
We can also create a shortest path spanning tree from a point on an edge. Consider edge uv of G and
any point χ on uv. Let Tχ be a shortest path spanning tree from χ such that dTχ
(χ, v) = dG(χ, v) for all
v ∈ V (G).
There are an infinite number of points along any single edge, and we can create a shortest path spanning
tree from each of these points. However, there are only a finite number of possible spanning trees of G (at
most n
n−2
from Monday’s class); therefore, there will be many points χ and χ
0
for which the shortest path
spanning trees Tχ and Tχ0 are identical.
Furthermore, let’s say two spanning trees T1 and T2 are equivalent if for all x ∈ V , dT1
(u, x) = dT2
(u, x)
and dT1
(v, x) = dT2
(v, x). Let S be a set of spanning trees. Let’s define a class of equivalent trees to be a
maximum subset of S such that all trees in the subset are equivalent to each other.
Let Suv be the set of all shortest path spanning trees that are rooted at a point along the edge uv. How
many separate classes of equivalent spanning trees can there be in Suv? Prove your answer.
