edges in a k-partite graph

Question

Let $G$ be a simple $k$-partite graph with parts of sizes $a_1$, $a_2$, ..., $a_k$. Show that $$m \le \frac{1}{2} \sum_{i=1}^{k}{a_i(n-a_i)}$$

How do I approach this problem? What is the relationship between edges and part sizes in a $k$-partite graph?

Answer 1

Define $G = (V,E)$, with $V = \bigcup_{i=1}^k V_i$ and $V_r \cap V_s = \varnothing$ for $r \neq s$. Using the identity $$\sum_{v \in V}d(v) = 2m,$$ and the fact that $d(v) \leqslant n-a_i$ for $v \in V_i$,

we get \begin{align} m & = \frac{1}{2}\sum_{v \in V}d(v) \\ & = \frac{1}{2} \left(\sum_{v \in V_1}d(v) + \dots +\sum_{v \in V_k}d(v) \right) \\ & \leqslant \frac{1}{2}\left(\sum_{v \in V_1}(n-a_1) + \dots +\sum_{v \in V_k}(n-a_k) \right) \\ & = \frac{1}{2}\left(a_1(n-a_1) + \dots +a_k(n-a_k) \right) \\ & = \frac{1}{2}\sum_{i=1}^k a_i(n-a_i). \end{align}