Section Projects: Tree Equivalence and Kruskal's Theorem
Equivalent Tree Definitions. In the next few problems, we investigate how one might discover and prove Theorem 7.6.
Problem 7.17.
Draw five different connected graphs in which every edge is a cut edge. Count the number of edges and the number of vertices. Make a conjecture for the relationship between the number of vertices and the number of edges in such a graph.
Our goal is to find some easily verifiable conditions for a graph to be a tree.
Problem 7.18.
Show that if an edge of a connected graph is part of a circuit, then that edge is not a cut edge.
Problem 7.19.
Show that if a connected graph with more than one vertex has no circuits, then every path either ends in a degree \(1\) vertex or can be extended to a path that ends in a degree \(1\) vertex.
Problem 7.20.
Let \(G\) be a connected graph with \(n\) vertices and no circuits. Prove by induction on \(n\) that \(G\) has exactly \(n-1\) edges.
Problem 7.21.
Show that if the number of edges in a connected graph is one less than the number of vertices, then it is a tree.
Problem 7.22.
Use the facts you have established to prove the following theorem by showing that line 1 implies line 2, which implies line 3, which implies line 4, which implies line 1.
Theorem. Equivalent Tree Definitions. For a connected graph \(G\text{,}\) the following are equivalent.
\(G\) is a tree.
Every edge of \(G\) is a cut edge.
\(G\) has no circuit.
The number of edges in \(G\) is one less than the number of vertices.
Kruskal's Theorem. In the next two problems we will look at Kruskal's Theorem to see why the spanning tree obtained from Kruskal's Algorithm always has the smallest total weight of any spanning tree. In the figure below is an arbitrary spanning tree \(S\) for the graph in Figure 7.23. We would like to see why its total weight must be no less that that of the spanning tree obtained from Kruskal's Algorithm.
Problem 7.24.
Apply Kruskal's Algorithm to the graph in Figure 7.2 to obtain a minimum weight spanning tree \(T\text{.}\) As you do it, number the edges in the order you add them. Find the total weight of \(T\text{.}\)
Problem 7.25.
What is the total weight of the spanning tree \(S\) in Figure 7.23? Make a copy of \(S\) in pencil. Transform the spanning tree \(S\) into \(T\) by adding the edges of \(T\) to it, in the order you numbered them, each time removing an edge not in \(T\) that closes a circuit. As you do so, fill out a table like this:
When you have finished transforming \(S\) into \(T\text{,}\) add up the reductions you made in the weight of \(S\text{.}\) Now subtract this amount from the original weight of \(S\) to see if you get the weight of \(T\text{.}\) Write this out neatly so that it is clear what you have done. \((\)If you can reduce the weight of \(S\) to get the weight of \(T\text{,}\) then you know that \(T\) must have smaller weight than \(S\text{!}\)\()\)
Problem 7.26.
Using Problem 7.25 as a guide, prove that Kruskal's Algorithm always produces a minimal spanning tree.