0
$\begingroup$

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?

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

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.