# For a graph to be connected, you need at least n-1 edges rigorous proof

This fact seems obvious but I was unsure how to go about proving it very rigorous.

Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition:

If a graph is connected then $|E| \geq n-1$, i.e. it needs at least n-1 edges.

The fact seems simple and maybe obvious but I was unsure how to rigorously prove the implication. Maybe contrapositive?

The issue that I have with it is that it nearly feels like an axiom. Is there a way to conclude this without assuming it to be true?

One way to prove this is by showing that a graph on $n$ vertices with $m$ edges has at least $n-m$ connected components. The proof is by induction on $m$. If $m = 0$ the graph is empty and no vertex is connected to any other. Now suppose that the claim is true for $m$ edges, and consider some graph with $m+1$ edges. Let $C_1,\ldots,C_k$ be its connected components. Choose some arbitrary edge $e = (x,y)$, and suppose that $e \in C_i$. Let $A$ be the set of vertices $v \in C_i$ for which there is a path from $x$ to $v$ not passing through $e$. Any vertex in $C_i \setminus A$ has some simple path to $v$ which passes through $e$. This path ends at $e$, and so there is a path from $y$ to $v$ not passing through $e$. This shows that both $A$ and $C_i \setminus A$ are connected even if we remove $e$. Other connected components are not effected by the removal of $e$ (since $e$ doesn't touch any of their vertices), and so if we remove $e$, the graph has at most $k+1$ connected components. The induction hypothesis shows that $k+1 \geq n-m$, and so $k \geq n-(m+1)$, proving the inductive step.
If a graph is connected then it has one connected component, so $n-m \leq 1$, that is, $m \geq n-1$.