There does not exist a bipartite cubic planar graph on $10$ vertices : I want to prove :
There does not exist a bipartite cubic planar graph on $10$ vertices.
I saw same question registered at this site, but I couldn't understand all of solution.
According to Euler's theorem, $v = 10, e = 15, f = 7$. but why it should be six of size $4$ and exactly one of size $6$? and how it induce $K_{3,3}$?
 A: A face in a bipartite graph must have an even number of sides, and a thing with only two sides is not allowed. (If it was allowed, then a 10-cycle with alternately single and double edges would be a solution). Therefore every face has at least four sides.
There are 30 sides in total to distribute among the 7 faces (because each of the 15 edges is a side of two faces. 7 faces with 4 sides each have 28 sides in total, so there are two extra sides to distribute. But since the face degree is always even, the two extra sides must go on the same face, there must be one face with 6 sides, and the remaining 6 faces have 4 sides each.
Now start by drawing the face with 6 sides. That uses up 6 nodes. Since the graph is cubic, each of these nodes have an extra neighbor. But if those neighbors are all different, then there would be at least 12 nodes in the graph which is too many.
Therefore, there must be a pair of corners of the hexagon that share a neighbor outside the hexagon. Since the graph is bipartite, this is only possible if these two nodes are separated by one corner in the hexagon. But then it's impossible for the extra leg of the corner between them to connect to anything, which is absurd. So the graph cannot exist.
