planar regular bipartite graph

Question

(a) Prove that there exists a 3-regular planar bipartite graph $G$ with $4n$ vertices for all $ n\geq 3$.

(b) Prove that does not exist a 3-regular planar bipartite graph with $10$ vertices.

The only idea had for (a) was that is enough to prove the claim for a 3-regular bipartite graph with $12$ vertices because then we add $2$ vertices. The only theorem I knew about planar graphs is Kuratowski and that if the graph is planar then $ m <3n-6$. I can't use the fact that we are looking for a bipartite graph.

For (b): $2m =\sum deg(v) =3\cdot 10 =30$ so it is $m=15$.

Answer 1

$m\lt3n-6$ does not imply planarity; rather, planarity implies $m\le3n-6$.

Make a cycle of $4n$ vertices, calling them $1,2,\dots,4n$ in order around the cycle. Join $4n$ and $3$, $4n-1$ and $4$, $4n-2$ and $5$, etc., $2n+3$ and $2n$; all of these can be drawn inside the cycle. Then go outside the cycle to join $1$ and $2n+2$, and $2$ and $2n+1$. That does (a).

Answer 2

For (b), you can use Euler's formula ($n - m + f = 2$) to show there must be 7 faces, and hence can say there must be 6 of size 4 and exactly one of size 6. Since there are 4 vertices not in that face it is then possible to deduce the existence of a $K_{3,3}$...

An alternative approach for (a) is to start with any planar cubic bipartite graph with $4n$ vertices and then choose any face, call it $F$. Carefully take two edges from $F$ and subdivide those edges with two vertices and join them across $F$ to create a planar cubic bipartite graph with $4n+4$ vertices.

Further edit for (b): The four vertices $\it not$ in $S$ (the face of size 6) must be two from each of the parts (red and blue) and the only possibility is for them to induce a $P_4$. Consider the red end of the $P_4$ which has to be joined to two blue vertices of $S$ and so there must be a red vertex in $S$ which is between the two blue vertices. From there you can prove that there must be a $K_{3,3}$ whichever face the $P_4$ is in.

Answer 3

In the hope to provide some more visual intuition for the answers to (a) by Gerry and ET1, let me just post the pictue of a 6-prism.

A prism over a 2n-gon has 4n vertices, and the graph is bipartite and 3-regular.