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!
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.