1,210 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. 

1 Answer

Best answer
3 votes
3 votes

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

Related questions

3.3k
views
1 answers
0 votes
neha singh asked Oct 11, 2016
3,335 views
What is largest number of maximal independent set of complete bipartite graph K(4,2)?a)2b)3c)4d)6
281
views
2 answers
0 votes
1.9k
views
0 answers
1 votes
srestha asked Sep 21, 2018
1,850 views
Which of the following complete bipartite graphs will have Hamiltonian cycle?$a)K_{3,3}$b)K_{2,4}$