# Proving that each graph contains a spanning tree?

as a part of Discrete Mathematics course we are taking an introduction to graph theory. We got this question for homework:

Let $G=(V,E)$ a connected graph. Prove that there exist a sub-graph $H$ of $G$ such that $H$ is a tree and include all of $G$'s vertices.

So, I immediately thought of the process of removing all the edges of $G$ such that their removal will not increase the number of connected components, thus insuring that we have a connected cycle-free graph, which is a tree.

My question: is describing this process makes a valid proof? This course is only introductory so we're not very formal, but I still want to make sure that the possibility of this process on any connected graph proves the existence of a tree.

-

You could try to formalize this by induction: Prove that in any connected graph with m edges, there's some spanning tree. You could use the case with no edges (a single node) as your base case, then for your inductive step claim that either a graph with (m + 1) edges, either it's already a tree or you can delete an edge that doesn't disconnect the graph, use the IH to find spanning trees for what remains, and then connect the graph together.

Another inductive approach: Try proving it for the case where you have a graph with one node, then show that in a graph with (n + 1) nodes, you can single out some node, remove it from the graph, and use the inductive hypothesis to get subtrees for each of the connected components remaining. You can then join them together into a tree.

Since this is a homework question, I'll leave this as an exercise to the reader. :-)

-

If you use induction on the edges and then when you remove any edge then G will be a G=(v, E-k) that E-k < E then according to the hypothesis of your induction it will be true. And if there wasn't any edge that we can remove then G is a tree and H=G.

-

You can turn an algorithm for constructing an object into an existence proof as follows:

1. State the algorithm
2. Prove that the algorithm eventually terminates
3. Prove that the result of the algorithm satisfies the desired properties

Your algorithm can be described in pseudocode as follows:

SPANNING_TREE(G):
let H = G
while H contains an edge e whose removal does not disconnect the graph:
remove e from H
return H


Note that to be more rigorous you would want to describe how to find an edge to remove (if one exists). Then all you need to do is prove that SPANNING_TREE terminates and that the result really is a spanning tree of the input graph.

-