Proving a bipartite graph is not planar

Question

I have drawn the bipartite graph K3,3. And I need to prove this graph isn't planar. I used contradiction, assuming it was planar, using Eulers formula to prove it wasn't planar.

I concluded my graph should have 5 faces according to Eulers formula, I then labeled faces on my graph to conlcude there are >5 faces in this graph, and it is clearly not planar.

Is this sufficient enough to prove my graph is not planar?

Answer 1

This is the key observation: if a planar bipartite graph has at least one cycle, every face has at least four edges. Counting each edge by its incident faces shows that $4f \le 2m$. This inequality combined with Euler's formula gives $4 = 2n - 2m + 2f \le 2n - m$. However, $K_{3,3}$ has $n=6$ and $m=9$, and so it is not planar.

Answer 2

You should first find the amount of vertices, edges, and faces in your graph. Then use euler's formula and if you do not get 2, the graph is not planar.