133 views

How to determine for which m, n the complete bipartite graph $Km,n$ is planar?

I am getting two answers from two sources:-

1. A complete bipartite graph $Kmn$ is planar if and only if m<3 or n>3. Source: https://www.javatpoint.com/planar-and-non-planar-graphs#:~:text=A%20complete%20bipartite%20graph%20Kmn%20is%20planar%20if%20and%20only%20if%20m%3C3%20or%20n%3E3.
2. Since $K3,3$ is not planar, but $K2,n$ is planar for every n, we have that Km,n is planar if and only if m ≤ 2 or n ≤ 2. Source: http://www.matthewkahle.org/download/file/fid/573

Need a proper proof of the solution.

Graph is planar if we can draw the graph on a 2-D plane without overlapping edges.

For $K_{1,n}$ are palanar because we can draw planar graph like,

For $K_{2,n}$ are also planar, we can draw them like

We know that $K_{3,3}$ is non-planar. So for every $m>=3$ and $n>=3$  we get $K_{3,3}$ as sub-graph so it is not planar. [According to Kuratowski's Theorem]

Kuratowski's Theorem states that a graph is planar if and only if it contains no sub-graph of $K_5$ or $K_{3,3}$

by

### 1 comment

Thanks. So we can say that:-

$\sim planar \iff m>=3$ $\wedge$ $n>=3$ OR,

$planar \iff m<3$  $\vee$ $n<3$

1
2,733 views