Prove that for every even $n\ge 4 $, there exists a planar, connected and 3-regular graph with $n$ vertices

670 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

enter image description here

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

0
On

Here is a visual solution:

For $n=4k$: enter image description here

And for $n=4k+2$: enter image description here