Every connected graph contains a spanning tree

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?

• What if you take the sub graph of one edge? – Alex R. Jan 24 '16 at 19:48
• Nothing. Just throw away one of the edges and you are left with a spanning tree. – TomGrubb Jan 24 '16 at 19:48

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.

• Ok, thank you very much, I just confused between induced subgraph and spanning subgraph – uuuuuuuuuu Jan 24 '16 at 19:57
• In fact, rewording this a bit, this is a proof by induction (on the number of edges) of the theorem. – YoTengoUnLCD Jan 24 '16 at 20:03

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.