Use induction on the number of edges to prove that every con

Use induction on the number of edges to prove that every connected graph contains a spanning tree. (Note that a spanning subtree is a subgraph T of G such that T is a tree and V(T) =V(G).)

Solution

By induction on the number of edges. If G is connected and has zero edges, it is a single vertex, so G is already a tree.

Now suppose G has m1 edges. If G is a tree, it is its own spanning tree. Otherwise, Gcontains a cycle; remove one edge of this cycle. The resulting graph G is still connected and has fewer edges, so it has a spanning tree; this is also a spanning tree for G.

In general, spanning trees are not unique, that is, a graph may have many spanning trees. It is possible for some edges to be in every spanning tree even if there are multiple spanning trees. For example, any pendant edge must be in every spanning tree, as must any edge whose removal disconnects the graph (such an edge is called a bridge.)