Paragraph

How do we know? We can give an algorithm for finding a spanning tree! Start with a connected graph \(G\text{.}\) If there is no cycle, then \(G\) is already a tree and we are done. If there is a cycle, let \(e\) be any edge in that cycle and consider the new graph \(G_1 = G - e\) (i.e., the graph you get by deleting \(e\)). This tree is still connected since \(e\) belonged to a cycle, there were at least two paths between its incident vertices. Now repeat: if \(G_1\) has no cycles, we are done, otherwise define \(G_2\) to be \(G_1 - e_1\text{,}\) where \(e_1\) is an edge in a cycle in \(G_1\text{.}\) Keep going. This process must eventually stop, since there are only a finite number of edges to remove. The result will be a tree, and since we never removed any vertex, a spanning tree.