I know that, if there exists such a graph, its number of faces $C$ satisfy that $C=n/2 +2$, though I don't know whether it is helpful in this proof or not.
I thought of using induction, starting from a graph 3-regular and connected with $n=2\cdot (k+1)$ , then remove two vertices to apply the induction hypothesis, however by doing that the graph wouldn't be 3-regular.


For $n=4$ the complete graph $K_4$ will do, for larger $n=2m$ an $m-gonal$ prism will do.