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.