in Graph Theory
133 views
0 votes
0 votes

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. 

in Graph Theory
133 views

1 Answer

3 votes
3 votes
Best answer

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}$

selected 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$
3
3

Related questions