Help with this problem please

Question

I have to proof that in a graph $G$, if $n$ is the order and $m$ the size, if $G$ is connected then $$m \geq n -1.$$

I had thought about doing it by contradiction and then finding that if it is connected, the incidence matrix must have at least $n - 1$ edges, but I have the feeling that there is a more simple and understandable way of proving this, can you help me find it?

Thanks a lot

Answer 1

Hint: If you erase one edge, you can prove that you get at most two components.

This suggests induction by the number of edges...Don't forget to cover both the 1 and 2 components cases...

Answer 2

You can build up a connected graph by adding edges one at a time. The first edge connects two vertices. Each additional edge (which you can choose to have one end at an already connected vertex) adds at most one new vertex. Count.

Be careful to explain how you are using the connectedness, if you use this method.