Every connected graph contains a spanning tree

Question

If we consider two vertices connected by two edges, then this graph doesn't contain a spanning tree. Then what is wrong with the theorem?

Answer 1

In general, for any connected graph, whenever you find a loop, snip it by taking out an edge. The graph is still connected. Since each step necessarily reduces the number of loops by 1 and there are a finite number of loops, this algorithm will terminate with a connected graph with no loops, i.e. a spanning tree.

Answer 2

The algorithm Alex R. mentioned is known as the Reverse-Delete algorithm. Kruskal's algorithm works in reverse. Take the edges of the tree, and add them in one at a time. If an edge creates a cycle, discard it. The algorithm returns a spanning tree, so long as $G$ is connected.

You then have to prove this algorithm actually returns a spanning tree (as you would have to with the Reverse-Delete algorithm). The benefit of using an algorithm here and a constructive proof is that it provides some intuition as to why a connected graph has a spanning tree. In this case, induction doesn't necessarily give you that intuition.

In general, when you can give a constructive argument, it is best to do so. There are problems in graph theory where we want to decide whether a specific type of graph exists. In certain cases, many of the necessary conditions are satisfied (and even sufficient conditions), but we struggle to provide a construction. It's hard to argue about a proof if it provides you the graph for which you are looking.