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\).
Start with any edge (and its two adjacent vertices) in \(G\). Call this subgraph \(T_1\). Explain why \(T_1\) has no cycles.
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\).
Repeat step (b) until you have a subgraph \(T = T_{n-1}\) of \(G\) with \(n\) vertices. Explain why…
\(T\) is cycle-free
\(T\) is connected
This graph \(T\) is called a spanning tree for \(G\).
Draw a graph \(G\) with \(8\) vertices and \(13\) edges.
Apply the above algorithm to your example graph to find a tree subgraph \(T\).