Problem 1: Prove that the graph obtained from Kn by deleting one edge has (n − 2)nn−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 nn−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.
