Math 301: Trees, I

Class date: Wednesday, November 13, 2019

Let \(G\) be a connected graph with \(n\) vertices. We’re going to find a tree subgraph \(T\) of \(G\) that contains all vertices of \(G\).

  1. Start with any edge (and its two adjacent vertices) in \(G\). Call this subgraph \(T_1\). Explain why \(T_1\) has no cycles.

  2. Say we have a tree subgraph \(T_i\) of \(G\), where \(T_i\) has \(i+1 < n\) vertices. Explain why there is an edge that we can add to \(T_i\) to produce a new tree subgraph \(T_{i+1}\) of \(G\).

  3. Repeat step (b) until you have a subgraph \(T = T_{n-1}\) of \(G\) with \(n\) vertices. Explain why…

    1. \(T\) is cycle-free

    2. \(T\) is connected

    This graph \(T\) is called a spanning tree for \(G\).

  4. Draw a graph \(G\) with \(8\) vertices and \(13\) edges.

  5. Apply the above algorithm to your example graph to find a tree subgraph \(T\).