Hint: Consider a spanning tree of the graph. What happens when you add edges?
Let me first define what a tree is formally: A tree is a connected graph which contains no cycles. A leaf is a vertex of the tree which has degree $1$.
There are quite a few definitions which are equivalent, I shall choose one of the simplest and the one most suited for our application here.
Here are a few things which you will need to prove. These are not very long, if you have a proof which is very complicated then you've probably gone wrong somewhere. I've added hints in spoiler tags. Perhaps one thing I should mention. Do not let the abstract terms and definitions bog you down; a tree is exactly what you think it is (no, not the things outside). Your intuition will serve you well, you only need to take a bit of care to convert your intuition properly into a proof.
1. Every tree has at least two leaves.
Hint: Consider "walking" through the tree. Can we continue this process indefinitely? Where must we end up?
2. A tree on $n$ vertices has precisely $n-1$ edges.
Hint: Use the above fact and induction.
3. Adding any edge to a tree will create a cycle.
Hint: If you add an edge $(u,\ v)$ then can you find two different paths now from $u$ to $v$?
Now a spanning tree is a connected, cycle-less subgraph of a connected graph which contains every vertex.
4. Every connected graph has a spanning tree.
Hint: Induct on the number of edges.
These should be enough to provide a very rigorous proof of your fact.