2,359 views
0 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 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
Position:
Show:

Related questions

0 0 votes
1 1 answer
3.9k
3.9k views
neha singh asked Oct 11, 2016
3,947 views
What is largest number of maximal independent set of complete bipartite graph K(4,2)?a)2b)3c)4d)6
0 0 votes
1 1 answer
240
240 views
GO Classes asked Oct 16, 2024
240 views
A way to transform one undirected simple graph into another is by obtaining its subdivision. Intuitively, the subdivision of an undirected graph $\mathrm{G},$ denoted $\t...
0 0 votes
2 2 answers
649
649 views
1 1 vote
0 0 answers
3.3k
3.3k views
srestha asked Sep 21, 2018
3,324 views
Which of the following complete bipartite graphs will have Hamiltonian cycle?$a)K_{3,3}$$b)K_{2,4}$