Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the existence of a $6-cycle,C_6$ in $G$ first.

I cant really understand why bipartile is useful here and what to do with existance $6$-cycle. I know that if there exist $K_{3,3}$ or $K_5$ as a subgraph in $G$, then it is not a planar. However the problem is there are so many configuration of a $10$ vertice graph with $3$ degree each vertices. Any assists would be appreciated. Thanks!

  • $\begingroup$ Bipartite is not just useful, but necessary, as it's not hard to find a 10-vertex planar graph with all vertices of degree 3. Try it! $\endgroup$ – Gerry Myerson Dec 11 '14 at 8:20

There is clearly no $K_{5}$ in $G$, as bipartite graphs have no cycle of odd length. So our options are to find explicitly a $K_{3, 3}$, or to provide a deletion-contraction yielding $K_{3, 3}$ or $K_{5}$ exactly. The first approach is Kuratowski's theorem, and the second is Wagner's Theorem. I will employ Wagner's Theorem here.

By the Handshake Lemma, we know that $G$ has $15$ edges. Observe that each partition must have $5$ vertices to utilize all the edges (notice that a $(7, 3)$ partition only utilizes $9$ edges and a $(6, 4)$ partition only utilizes $12$ edges). By the pigeonhole principle, every pair of vertices in one partition must share at least one neighbor. Draw out the graph to see this.

So start at $v_{1}, v_{2}$ in the first partition. Call their neighbor $v_{6}$. Now $v_{6}$ and $v_{7}$ in the second partition must share $v_{1}$ as a neighbor. As $v_{7}$ has degree $3$, it must be adjacent to some $v_{3}$ in the first partition. We add $v_{3}$ to our construction, leaving us with: $v_{1} - v_{6} - v_{2} - v_{7} - v_{3}$.

We know that $v_{3}, v_{1}$ have a common neighbor $v_{8}$ in the second partition, completing our $C_{6} \in G$.

Now finish constructing the graph by making the remaining four vertices into a $C_{4}$ instance. Then add in the remaining $5$ edges accordingly.

Observe that if we contract one partition into the other, then we have $K_{5}$. That is for each vertex $v$ in a partition, contract each of $v$'s edges. And so by Wagner's Theorem, $K_{5}$ is not an excluded minor, so $G$ is non-planar.


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.