Does this example of "reverse induction" work?

Question

Say we've shown that some statement $P(1)$ is true. Suppose that we can show $P(m) \iff P(m-1)$. Then, we will have shown $P(m) \iff P(1)$, so $P(m)$ is true. This makes sense, right?

So, with more context, let's say that we would like to show a graph that depends on $n$ with certain properties exists. Then, if we show that it exists for $n = 1$ and then we show that if a graph exists for arbitrary $n$ then we may get the $n-1$ case through edge/vertex deletions, can we say it holds for all $n \in \mathbb{N}$? To be more precise, is this general vertex/edge deletion a "reversible process"?

Answer 1

False theorem. For all $n$, there is a simple graph with $n$ vertices and $n^2-1$ edges.

Proof. This exists for $n=1$: take the graph with $1$ vertex and no edges.

Suppose it exists for $n$ vertices. Then by deleting a vertex of some degree $k$, and then deleting $(2n-1)-k$ more edges arbitrarily, we get a simple graph with $n-1$ vertices and $(n-1)^2-1$ edges.

---

This is an instance of the problem. In general, deleting things is not reversible, since you may end up getting from an impossible graph to a possible graph by deleting the places where it's impossible. Even in cases where it is reversible, your proof would be cleaner if you constructed the graphs "forward" rather than "backward".

Answer 2

In your first paragraph, you stated showing implication in both directions and the statement makes sense. In fact, the forward implication is the standard case in normal induction

However, in your second paragraph, you showed only an implication for the reverse direction. You can only claim that if you proved the case for some fixed $k$, and then if $P(k)\implies P(k-1)$, the statement holds true for all $n\leq k$. This is known as backwards induction. You can't say anything about $n>k$.

(Correct me if my interpretation of what you meant is wrong. Because if what you want to show is the existence of a graph and you have shown a graph exist for some arbitrary $k$, you don't need induction?)

Another common induction technique in graphs is Forward-Backward Induction.