Why does this proof by induction work here?

Question

The Problem is: Prove that graph $G=(V,E)$ has at least $|V|-|E|$ components. I've seen the solution here https://math.stackexchange.com/a/492183:

This is a part of the proof:

"Take a graph with $n$ vertices and $k+1$ edges. Pick any edge and look at the graph without that edge. The reduced graph has $n$ vertices and $k$ edges, and so by the inductive hypothesis, has at least $n-k$ components. Placing the edge back in can reduce the number of components by at most one, meaning the original graph has at least $n−k−1=n−(k+1)$ components. "

I dont understand why the proof by induction work here, till now i just had to use induction with sums. I somehow miss the logical step why it still work for $k+1$ edges, how it is a proof just by saying "the original graph has at least $n−k−1=n−(k+1)$ components"

Answer 1

Induction is a general proof technique, which is not specific to sums. Suppose you want to proof some property holds for all $n$. If you know that it holds for $n=0$ (or $1$ if you like) and that, assuming it holds for a given $n$, you can reduce the problem of proofing it for $n+1$ to the requirement that it holds forn $n$, then you are done. Thinking of induction as some kind of proof-step-domino made it clear for me once and for all. I mean, building a chain of dominos, you have to make sure that if one falls (induction hypothesis), the next one does too (induction step), so when the first falls (induction base), the whole chain collapses (proof for all $n$).

Answer 2

For each $n$ (number of vertices on the graph), the answer linked proves the statement by induction on the number $k$ of edges on the graph.

Proof by induction has two components: a base case and an inductive step.

The base case in the linked answer is the case $k_0=0$. A graph with $n$ vertices and no edges obviously has $n=n-0$ components, so the statement is true for the base case.

Now, for the inductive step, one assumes that the statement is true for some value of $k\geqslant {k_0}^{[1]}$; this is the induction hypothesis. With the induction hypothesis, one then proves that the statement is also true for $k+1$.

The linked answer considers a graph with $n$ vertices and $k+1$ edges, and from that graph they delete an edge $e$. The resulting graph has $n$ vertices and $k$ edges, and so we may apply the inductive hypothesis to conclude that it has at least $n-k$ components.
If we now reinstate the edge $e$, either we still have at least $n-k$ components, or the edge connects two previously disconnected components, reducing the number of components by $1$ to at least $n-k-1 = n-(k+1)$.
Regardless of the situation, we see that the statement still holds true, and the proof is complete.

---

$^{[1]}$: We may assume the statement is true for all values of $K$ with $0\leqslant K\leqslant k_0$. In some cases, this helps with the proof.