Determine exactly the values of $m$ and $n$ for which the complete bipartite graph $K_{m,n}$ is planar.
I have tried doing this by drawing different complete bipartite graphs and just using guess and check to see if planar or not. Obviously this isn't working and would like to see how this is done.
Best Answer
The graph $K_{1,n}$ is planar for all $n$ since it's just a star graph.
The graph $K_{2,n}$ is planar for all $n$. To see this, draw $n$ vertices in a straight line in the plane, and draw two more vertices, one on each side of the line, and connect these two vertices to each vertex on the line.
Every other case deals with $K_{n,m}$ where $n,m\geq 3$. But then this graph must have $K_{3,3}$ as a minor so it is nonplanar by Wagner's theorem. Or it's nonplanar by Kuratowski's theorem if you'd rather say "subgraph" instead of "minor".