Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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. :-)

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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