6
$\begingroup$

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

$\endgroup$

4 Answers 4

7
$\begingroup$

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

$\endgroup$
5
  • $\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, 2012 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, 2012 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$ Feb 3, 2012 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$ Feb 3, 2012 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, 2012 at 11:53
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I like the approach to (a), but I can't connect the dots to see (b). $\endgroup$ Feb 4, 2012 at 0:11
4
$\begingroup$

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)'}.)

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .