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

  • $\begingroup$ 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. $\endgroup$ – passenger Feb 3 '12 at 11:27
  • $\begingroup$ 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. $\endgroup$ – passenger Feb 3 '12 at 11:36
  • $\begingroup$ By the way, for (a), $n\ge2$ will do. The cube is a 3-regular planar bipartite graph with 8 vertices. $\endgroup$ – Gerry Myerson Feb 3 '12 at 11:41
  • $\begingroup$ Your try for (b) shows that one attempt to build a graph fails. It doesn't show that every attempt must fail. $\endgroup$ – Gerry Myerson Feb 3 '12 at 11:42
  • $\begingroup$ 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}$.... $\endgroup$ – 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.

  • $\begingroup$ I like the approach to (a), but I can't connect the dots to see (b). $\endgroup$ – 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)'}.)

  • $\begingroup$ This is the same graph as in the accepted answer. $\endgroup$ – Mangara Dec 2 '15 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.