Constructing Cubic Graphs of Even Order The problem is to show how to construct a cubic graph of v vertices whenever v is even. (for v $\ge4$)
I think I'm supposed to use a degree sequence to aid my construction, but I need help getting started.
 A: We'll proceed by induction.
The smallest possible cubic graph is the complete graph on four vertices. This is our base case.
Now, given any cubic graph $G$ on $v$ vertices, we want to construct one on $v+2$ vertices. Insert the two new vertices $x$ and $y$ with an edge between them, but not yet connected to $G$. Remove any two adjacent edges from $G$ (i.e. two edges that have a common vertex). Notice $G$ now has two vertices of degree $2$ and one vertex of degree $1$ (not counting $x$ and $y$). Connect $x$ to one of the degree $2$ vertices and $y$ to the other. Finally, connect both $x$ and $y$ to the degree $1$ vertex. After all this patching, we now have a new cubic graph on $v+2$ vertices.
A: In order to generate a cubic graph of even order ($n\equiv 0\pmod{2}$) we can generate a regular $n$-gon and then for each vertex connect it to the vertex directly opposite and the two vertices to either side; this will result in a connected cubic graph of even order and works $\forall n \in \mathbb{N} : n \equiv 0 \pmod{2}$ as required.
A: 
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
A: If you have a graph of 4 vertices and a graph of 6 vertices (both easy), you can combine these as separate components to achieve any even order greater than 4. If you need a connected graph, only slightly more work is required.
