edges in a k-partite graph 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? 

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}
