Proving that each graph contains a spanning 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. :-)