Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
Thank you very much for your answer. –  passenger Apr 27 '13 at 16:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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