2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Didn't follow the details of the proof, but the technique is a variant of proof by infinite descent. $\endgroup$ – dxiv Apr 11 '18 at 3:03
  • $\begingroup$ In your opening paragraph how do you know it’s false for n = 1 $\endgroup$ – Prince M Apr 11 '18 at 3:12
  • $\begingroup$ You said false for n in naturals but it looks like just n geq 2 $\endgroup$ – Prince M Apr 11 '18 at 3:14
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Good answer, I was thinking about proving exactly that statement $Q(k)$, and it seems this was the right approach. $\endgroup$ – Nico Apr 11 '18 at 18:10
2
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.