Does induction work for just the even natural numbers? I'm currently starting Hartsfield and Ringel's Pearls in Graph Theory, and have a question about a proof I put together for one of the exercises in the first chapter. The exercise is as follows:

Prove that for every even number n ≥ 4, there exists a graph with n vertices, with each vertex having degree = 3.

I thought that maybe I could prove this using some kind of extended form of induction where we show that the statement is true for n = 4, assume its true for n = k (with k = 2p, p ≥ 2), and from this show that it must be true for n = k + 2 (or n = 2(p + 1)). Here is my proof:

For the first step, it's easy to construct a graph with 4 vertices, each having degree = 3. All we need to do is create an edge from each vertex to the other three vertices. Next we assume that our statement is true for n = k = 2p, with p ≥ 2. We then add two vertices to the graph, which we'll call Vₖ₊₁ and Vₖ₊₂. Next we create edge Vₖ₊₁Vₖ₊₂, and further create edges Vₖ₋₁Vₖ₊₁ and VₖVₖ₊₂. At this point our two new vertices both have degree = 2, but now Vₖ and Vₖ₋₁ both have degree = 4. It is clear that we must remove two edges from our graph, edges to which Vₖ and Vₖ₋₁ are incident, respectively. We obviously can't remove the edges that we just created, because then we would have reversed the previous step entirely. Furthermore, if it exists, we can't remove the edge Vₖ₋₁Vₖ, for reasons that become clear only later. At this point we are left with (at least) two edges for each of Vₖ₋₁ and Vₖ that could be removed. By the definition of a graph, and by the fact that each vertex in question is an endpoint of two edges which can safely be removed, let us select vertices Vₘ and Vⱼ, to which Vₖ₋₁ and Vₖ are connected, respectively. We also have that m ≠ j. So, as intended, let us delete edges Vₖ₋₁Vₘ and VₖVⱼ, which results in Vₖ₋₁ and Vₖ both now having degree = 3, as intended. However Vₘ and Vⱼ now have degree = 2. But remember that our two new vertices Vₖ₊₁ and Vₖ₊₂ have degree = 2 as well. At this point all we must do is create edges Vₖ₊₁Vⱼ and Vₖ₊₂Vₘ, and all of our vertices in our new graph with k+2 vertices has degree = 3, as desired. Thus we have shown that for every even number n ≥ 4, there exists a graph with n vertices, with each vertex having degree = 3.

This proof feels solid, but I'm not sure if this kind of induction works. My gut feeling is that it does, but I would love some input from someone who knows more than me. Thanks in advance.
 A: Sure!  In fact, you have some options here.
One option is to reformulate the problem such that it fits the typical scheme of induction. This is what SV-97 suggests in the Comments. So, specifically, you could define $P(n)$ as the claim that there exists a graph with $2n$ vertices, with each vertex having degree $= 3$, and now you'd have to prove that $P(n)$ is true for $n \geq 2$, i.e. prove that $P(2)$, and prove that $P(n) \to P(n+1)$
In fact, if you're concerned with the fact that the base case is $2$, rather than $0$ (or $1$, depending on how you were taught the induction scheme), you could even formulate $P(n)$ as the claim that there exists a graph with $2(n+2)$ vertices, with each vertex having degree $= 3$, and now you'd have to prove that $P(n)$ is true for $n \geq 0$, i.e. prove that $P(0)$, and prove that $P(n) \to P(n+1)$
However, I think what is more instructive is to realize that induction really doesn't have to fit any specific scheme, and that such reformulations are therefore not necessary either. Think about it: suppose we simply stick with $P9N)$ as the claim that there exists a graph with $n$ vertices, with each vertex having degree $= 3$, and suppose we show that $P(4)$, as well as $P(n) \to P(n+2)$. Well, then clearly we have shown the result for every even number $\geq 4$. So, we'd be done. And that is of course exactly what you did! So good job!
So yeah: I see this a lot, where people seem to think that induction always needs to be of a certain specific form. However, once you understand the basic idea behind induction, you may be able to figure out all kinds of iteration schemes ('domino stone set-ups') that'll completely cover some particular space of objects. This is why you can also do induction for all integers (by, e.g., showing $P(0)$, $P(n) \to P(n+1)$, and $P(n) \to P(n-1)$), for pairs of numbers (e.g. show $P(0,0)$, $P(x,y) \to P(x+1, y)$, and $P(x,y) \to P(x,y+1)$), or for objects that have nothing to do with numbers. See for example structural induction. Once you grasp the idea that 'weak mathematical induction' is just one form of induction, it'll really open your eyes.
