Proving a statement false by reverse induction

Question

On a recent graph theory assignment, I proved a statement false by "reverse" induction, showing that $P(2)$ was false, and that $P(k) \implies P(k-1)$ for $k>2$, thus, by the contrapositive, $\neg P(k-1) \implies \neg P(k)$, so $P(n)$ should be false for all $n\in \mathbb{N}$. This seems natural and like it should work in general, but after a quick Google search into "reverse induction", nothing like this proof technique showed, at least in the first few results. For completeness, here's the statement and my proof.

Does there exist a graph with vertex set $\{v_1,\dots,v_n\}$ such that $\deg(v_i)= i-1$ for $i=1,\dots,n$?

Answer: No

Proof: It does not work for $n=2$, since the first vertex would be a singleton, and the second vertex must have degree one, so it must be connected to the first, but this is impossible since the first vertex would then have degree one, a contradiction. Now for $n \geq 2$, Consider a labeling $\{v_1,v_2,\dots,v_{n+1}\}$, and suppose that there is a set of edges such that $\deg v_i = i-1$. Then by removing $v_{n+1}$ an all edges connected to it, we would have a graph with vertex set $\{v_1,v_2,\dots,v_n\}$, such that $\deg v_i = i-1$. The contrapositive of this however, is that if there is no vertex set on $\{v_1,v_2,\dots,v_n\}$, such that $\deg v_i = i-1$, then there is no graph with vertex set $\{v_1,v_2,\dots,v_{n+1}\}$ such that $\deg v_i = i-1$. As we have shown this for $n=2$, and the inductive step is proved, we must have that there are no graphs with vertex set $\{v_1,v_2,\dots,v_n\}$, such that $\deg v_i = i-1$ for $n \geq 2$.

Answer 1

Let me offer my five cents here.

(1) First of all, it appears to me that your proof is just the usual induction, rather than some kind of a "reverse" induction. You just need to understand what you proved: you applied the usual induction method to prove the statement $Q(n)=\neg P(n)$ for all $n\ge2$. Your basis was proving $Q(2)$, which is the same as demonstrating $\neg P(2)$, i.e. that $P(2)$ is false. And your induction step was proving $Q(k-1)\Rightarrow Q(k)$, which is the same as $\neg P(k-1)\Rightarrow \neg P(k)$, and for this particular proof you used a contrapositive method — you showed that $\neg Q(k)\Rightarrow \neg Q(k-1)$, i.e. that $\neg(\neg P(k))\Rightarrow \neg(\neg P(k-1))$, i.e. that $P(k)\Rightarrow P(k-1)$.

(2) Unrelated to your main question about interpreting such a "reverse" induction method, I still can't help but notice that you didn't have to use induction here at all. There's a pretty simple direct proof for this statement that works for any $n$. And you pretty much have it — just rephrase what you did for $n=2$ to apply to arbitrary $n$.

(3) And besides, I see a serious issue with your proposed proof, specifically with the following statement in it:

Then by removing $v_{n+1}$ an all edges connected to it, we would have a graph with vertex set $\{v_1,v_2,\ldots,v_n\}$, such that $\deg v_i=i−1$.

Here's my problem with this claim: if you removed a bunch of edges (the ones adjacent to $v_{n+1}$, which was given to have a nonzero degree), how come the degrees of the remaining vertices didn't change?

Answer 2

I think your confusion may come from you didn't specify the predicate statement correctly. You said:

$$P(k) \implies P(k-1).$$

So my question is: What's the domain of discourse of it? If you didn't make this clear, No one can prove/show that it is true. And you can't apply your "first domino", i.e. $P(2)$, to make it work like that of mathematical induction. So if you can show that for any $k\in \large\mathbb{N}$, the predicate is true down to $k-1=2,$ then yes your reverse induction technique should work, because you "connect" it to your "first domino".

Answer 3

It is induction :

Instead of $P(2)$ take $Q(2) = \neg P(2)$ and more generally $Q(k) = \neg P(k)$

You have shown that $Q(2)$ is true, and that $Q(k) \implies Q(k+1)$ so by induction $Q(n)$ is false for all $n \in \mathbb{N}$

Answer 4

This resembles a proof by infinite descent, but is a bit difficult to read. You do not need to use the contrapositive here. Instead, the "standard" approach is to structure the proof like this:

1. Prove that $n > 2$ (i.e. prove $\neg P(2)$, as you did). You would also have to rule out $P(1)$, but in this example $P(1)$ is actually true, so you should probably exclude that in the problem statement instead of the proof.
2. Assume that $\exists n > 2: P(n)$, and further assume that $n$ is the smallest such value. This second assumption is only allowed because we are working with positive integers; in the rationals or reals, there might not be any smallest value of $n$.
3. Prove $P(n - 1)$ from $P(n)$, also as you did.
4. Derive a contradiction because we previously assumed that $n$ was minimal.