b Prove the number of edges in a complete 3multipartite grap

(b) Prove the number of edges in a complete 3-multipartite graph Ki.m,n is lm+ In+ mn

Solution

Let V1,V2,V3 are the three partiate sets of Kl,m,n

of cardinality L,m and n respectively

Then each l vertices of V1 has degree m+n

Each m vertex of V2 has degree l+n

And each n vertices of V3 have degree l+m

Hence total degree sum is

l(m+n)+m(l+n)+n(l+m)

2(lm+mn+ln)

So by first theorem of graph theory

Number of edges is

lm+mn+ln