# planar regular bipartite graph

(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$.

-

$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).

-
Thank's for the answer. Sorry about the mistake, it was a typo. I know that planarity implies $m \leq 3n-6$. I will edit it. –  passenger Feb 3 '12 at 11:27
Here it is a try for (b) using the same idea as yours in (a). Consider a cycle with $10$ vertices say $1,2, \cdots ,10$ in order around the cycle. We add the edges $\{3,10 \},\{4, 9\},\{5,8 \}$ Then the only choice about $1$ and $2$ is the edges $\{1,6\}$ and $\{2,7 \}$. But now there is a subgraph $\{1,2,3,6,7,10 \}$ which is isomorphic (and so homeomorphic) to $K_{3,3}$. Hence our graph is not planar. –  passenger Feb 3 '12 at 11:36
By the way, for (a), $n\ge2$ will do. The cube is a 3-regular planar bipartite graph with 8 vertices. –  Gerry Myerson Feb 3 '12 at 11:41
Your try for (b) shows that one attempt to build a graph fails. It doesn't show that every attempt must fail. –  Gerry Myerson Feb 3 '12 at 11:42
Yes you are right. I didn't noticed that. Now I am trying to prove that there must be always a subgraph homeomorphic to $K_{3,3}$.... –  passenger Feb 3 '12 at 11:53

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.

-
Thank's for the answer. –  passenger Feb 3 '12 at 23:46
I like the approach to (a), but I can't connect the dots to see (b). –  Gerry Myerson Feb 4 '12 at 0:11

Another approach to (a). Start with a 2n-cycle with vertices 1, 2, 3, ..., 2n. Inside this, draw another 2n-cycle with vertices 1', 2', 3', ..., 2n'. Join vertices i and i' together for all i. This is a 3-regular planar bipartite graph of order 4n. (The two colour classes are {1, 3, 5, ..., 2n-1, 2', 4', ..., 2n'} and {2, 4, ..., 2n, 1', 3', ..., (2n-1)'}.)

-
Thank you very much for your answer. –  passenger Apr 27 '13 at 16:34