Question

. The complete m-partite graph 𝑲𝒏𝟏,𝒏𝟐,……,𝒏𝒎 has vertices partitioned into m subsets of 𝒏𝟏, 𝒏𝟐, … … , 𝒏𝒎 elements each, and vertices are adjacent if and only if they are in different subsets in the partition. For example, if m=2, it is our ever-trusting friend, a complete bipartite graph.

a. Draw these graphs: i. 𝑲𝟏,𝟐,𝟑 ii. 𝑲𝟐,𝟐,𝟑 iii. 𝑲𝟒,𝟒,𝟓,𝟏

b. How many vertices and how many edges does the complete 𝑲𝒏𝟏,𝒏𝟐,……,𝒏𝒎 have?

Answer 1

$K_{1,2,3}$

$K_{2,2,3}$

$K_{4,4,5,1}$

the degree of the top of the i-th share

$\sum\limits_{i\neq j}mj$

then

$S=\sum mj=> \sum\limits_{i\neq j}mj=S-mi$

the sum of the degrees of the vertex of the i-th part

$(S-mi)*mi=Smi-mi^2$

sum of degrees of all vertices

$\sum Smi-mi^2=S\sum mi-\sum mi^2=S^2-\sum mi^2=(\sum mi)^2 -\sum mi^2=\\ =\sum\limits_{i<j}2mi*mj$

the number of edges in the graph

$\frac{1}{2}\sum\limits_{i<j}2mi*mj=\sum\limits_{i<j}mi*mj$