# 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?

• Let you think. How many edges can arbitrary simple graph have? How many edges you need to deny to make set of $a_i$ vertices indepenent? How many edges are remaining? – Smylic Feb 8 '17 at 9:05

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$,