I was reading a practice problem set for a discrete maths course. It says:
By far, the most common mistake in this homework was using induction incorrectly for graph problems. When proving something about graphs by induction, you want to reduce from $n$ to $n − 1$. This is because you are proving a statement for all graphs of size $n$, and not just a specific graph. By proving something by constructing an $n + 1$ size graph using an $n$ size graph, you have only shown it for “one particular” graph of size $n + 1$, whereas you wanted to show it for all graphs of size $n + 1$. (By size, I mean either the number of vertices or the number of edges, whatever you are inducting on.)
Then they give an example:
We prove by induction on $n$ that if $|V| = n$ and $G$ is acyclic and $|E| = n − 1$, then $G$ is connected.
Base case ($n = 1$): This is trivial; $G$ consists of a single vertex and no edges.
Induction step ($n \geq 2$): First we will prove that $G$ has a leaf. Since $E \neq \emptyset$, we can pick a vertex $v \in V$ with $deg(v) > 0$. Start walking from $v$ until you reach a leaf, say $u$. This will happen because the graph is acyclic. Now, $G − u$ has $n − 1$ vertices and $n − 2$ edges, so we can use the induction hypothesis to conclude that it is connected. Adding $u$ to $G$ with the original edge keeps it connected.
Common Mistake: Constructing $n + 1$ vertex graph using an $n$ vertex graph in induction step. If you did this, you missed showing existence of a leaf, which is crucial.
I would have done it a bit different (rough outline):
Induction step $(n + 1)$: $G$ has $n+1$ nodes. We can find a leaf node $v$ with $deg(v) = 1$. $v$ has to exists because $G$ is acyclic. We obtain a subgraph $G'$ by removing $v$ from $G$. By induction we can assume $G'$ is connected. Adding $v$ again to $G'$ keeps the resulting graph $G$ connected, which proves the theorem for $n + 1$.
Is mine the wrong approach and I should have started from $n$? I thought in the inductive step for graph proofs, you usually start from a $n+1$ graph and for example reduce it to $n$ by removing a certain node/edge/...