I have my first assignment from my Languages and Automata class, and one of the problems is giving me a headache. I am supposed to prove a theorem using construction and induction. The proof by construction is a piece of cake (you could find my solution below) but the induction is not going so well. And this is supposed to be review . All help/hints will be appreciated; the theorem:

For each even numberngreater than 2, there exists a 3-regular graph withnnodes.

(as a side note, for those who don't know, a k-regular graph is a graph where each node has degree k, i.e. k incident edges)