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