Discrete math on multipartite graph

63 Views Asked by At

I am wonder about these problem

1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$

2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$

1

There are 1 best solutions below

0
On

Each vertex in $n_{i}$ has degree $\sum_{j=1, j \neq i}^{n} |n_{j}|$, as each vertex in $n_{i}$ is incident to every vertex in the other partitions. There are $|n_{i}|$ vertices in $n_{i}$, so that's why we multiply out. So by the handshake lemma, we get:

$$\sum_{i=1}^{n} (|n_{i}| * \sum_{j=1, j \neq i}^{n} |n_{j}|) = 2E$$