Maths - 1M - The chromatic no. of the complete bipartite gra...

The chromatic no. of the complete bipartite graph Km,n (m,n > 1) is...

|m-n|

min (m, n)

2

max(m, n)

1Comment
Habib Mohammad Khan @habibkhan 23 Sep 2016 11:19 am

In Km,n, we have each of m vertices of 1 set  , say m connected to each of n vertices of other set , say n and similarly for n set also . But no edge between vertices within set m or n.In other words , m and n are disjoint sets.So members of m can be coloured by 1 colour and the members of other set by other 1 colour.So 2 colours.

Also , we have a theorem which states that :

A graph is bipartite iff it is bichromatic.

Hence 2 should be correct.