Inductively the number of edges for a connected graph

Question

Claim: Every connected graph with $n$ vertices has at least $n - 1$ edges.

Proof by induction:

$P(n)$ = "Every connected graph with $n$ vertices has at least $n - 1$ edges." $\forall n \ge 1$

Base case: A graph with $1$ vertex has $0$ edges.

Inductive step:

1. Remove a vertex with the lowest degree and all its edges from the connected graph with $n + 1$ vertices.

2. The resulting graph has $n$ vertices. Apply the inductive hypothesis - this graph has at least $n - 1$ edges.

3. When you add the removed vertex back, it must connect to at least $1$ vertex in order for the overall graph to be connected.

4. The graph now contains at least $n - 1 + 1$ or $n$ edges

I'm new to graph theory, so I'm wondering if I completed this induction proof with the right steps. Any other methods or additions to this proof would also be appreciated. Thanks!

Answer 1

No, this doesn't quite work as written. You can't be sure that the graph that results from your step 1 is connected.

Hint. Prove this lemma:

Let $G$ be a connected graph with $m$ vertices. For every positive $n\le m$, there is a subgraph of $G$ that has $n$ vertices and $n−1$ edges.

by induction on $n$. Your goal then follows by setting $n=m$.

Answer 2

HINT: You have to work just a little harder, because the graph that remains after you remove a vertex need not be connected. However, your argument can be repaired to take that into account. Remove any vertex $v$; it needn’t be one of minimal degree. The remaining graph has $n$ vertices.

Say that it has $m$ components, $C_1,\ldots,C_m$, and for $k=1,\ldots,m$ let $n_k$ be the number of vertices in $C_k$. By the induction hypothesis each $C_k$ has at least $n_k-1$ edges, so the whole remaining graph has at least

$$\sum_{k=1}^m(n_k-1)=n-m$$

edges. What’s the minimum number of edges that you could have removed along with $v$?