Show that there exists a $5$-regular planar graph and a $5$-regular nonplanar graph.

Question

I'm working in the following graph theory excercise:

Show that there exists a $5$-regular planar graph and a $5$-regular nonplanar graph.

I'm thinking about the fact that the graph will have $|E(G)|= 5n/2$ and I've been trying to apply it to any theorem like $ 5n/2 ≤ 3n-6$ but I'm not sure this is the right way and also how to proceed, thanks in advance for any hint or help.

Answer 1

Hints

1. Recall that a graph is nonplanar iff it contains a subgraph isomorphic to $K_5$ or $K_{3, 3}$. The graph $K_5$ is $4$-regular; can you add vertices and edges to it to produce a $5$-regular graph?

2. Consider the icosahedron.