Graph Theory?

What is your basic idea?

How about an induction proof?
It's true for 4 (draw one)
Assume true for even n > 4.
Take such a graph on n points.
Take points A, B, C and D on the graph such that AB, BC and CD are all edges in that graph. You have to prove there are such points; it's not hard.

Take two more points X and Y. We'll construct a new graph on the n points + X and Y.
Remove edges AB, BC, and CD.
Add edges AX, BX, BY, CX, CY, and DY.
A, B, C, and D still have index 3, since for every edge you removed from them, you added one. A and D lost one edge and gained one. B and C lost two edges and gained two.
X and Y have index 3. They are connected to B and C, and A or D.
You have constructed a graph with n + 2 vertices, each of index 3. QED.