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/...


The "common mistake" described in the problem set instructions has nothing to do with whether your inductive step is based on $n$ and $n-1$ or $n+1$ and $n.$ It has everything to do with which number (the smaller one or the larger one) is the number of nodes in the arbitrary graph that you invoke in the inductive step. If you go from $n$ to $n+1$ (or if you go from $n-1$ to $n,$ for that matter!) by adding a node to an arbitrary graph, the proof is wrong. You must remove a node instead, as indeed you did.

Another vital thing to make sure of is that the inductive step can use the base case as its "input." In the problem set, this is done by making the inductive step use the assumption $P(n-1)$ to prove $P(n)$ for $n\geq 2.$ This means that when $n = 2$ in the inductive step, we use $P(1)$ (the base case) to prove $P(2).$ In your proof you need to specify that the inductive step applies for all $n \geq 1,$ not only for $n\geq 2,$ so that when $n=1$ you use $P(1)$ to prove $P(2).$ There are some classic fake proofs that rely on inductive steps that don't "connect" with the base case.

One thing I do not like about the proof style in either the problem set or your attempt is that you both launch into the inductive step without saying what the inductive assumption is, and simply mention later that something is true because of the inductive assumption. But both proofs are simple enough that I can infer what the inductive assumption was supposed to be, and that it "connects" with the base case.

| cite | improve this answer | |
  • $\begingroup$ Thank you, that is very nice explanation that clears up my doubts. Normally I would also have added a basecase though, I just wanted to say how I would rewrite the inductive step, but I take note of that. $\endgroup$ – Max Nov 28 '17 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.