Can I use induction by $|V|$ here?

Question

Show that any connected, undirected graph $G = (V,E)$ satisfied $|E|≥|V|-1$. Can I use math induction by $n = |V|$ here (remove and add vertex)?

Answer 1

Here's an argument (still induction on $|V|$) that proceeds by removing vertices:

The claim is clearly true if $|V|$ is $1$ or $2$. To proceed by induction we need to know that we can delete a vertex without disconnecting the graph. To see that this is always possible: Pick a node $\nu$ at random. Now for any node $n$ define its distance from $\nu$, $l(n)$, to be the length of a minimal path between $\nu$ and $n$. I claim that you can always delete any node $\hat n$ with maximal $l(\hat n)$: Take any two nodes other than the one you want to delete. Both have a path to $\nu$ that does not pass through $\hat n$ (otherwise they would be further from $\nu$ then $\hat n$ is). Since the two nodes can still reach $\nu$ once $\hat n$ is gone, they can reach each other.

Now the induction is easy: deleting $\hat n$ leaves a graph to which we can apply the induction hypothesis. When you restore $\hat n$ (along with all of the edges it was a part of) you increase $|V|$ by exactly $1$ and you increase $|E|$ by at least $1$.

Answer 2

Yes. The point is that you can build up the graph one vertex at a time, maintaining connectivity: if $u$ is a vertex you already have and $v$ is a vertex you don't, consider a path from $u$ to $v$ and add the first vertex on that path that you don't already have (together with the edges joining it to the vertices you already have).