## k-partite graph

### Set

 context $k\in\mathrm N$ context $V$ … set
 definiendum $\langle V,E\rangle \in \mathrm{it}(E,V)$
 inclusion $\langle V,E\rangle$ … undirected graph
 range $i,j\in\{1,\dots,k\}$ range $\bigcup_i X_i=V$ range $\forall i,j.\ X_i\cap X_j=\emptyset$ range $v,w\in V$
 postulate $\exists X_1,\dots,X_k.\ \forall u,v.\ \{u,v\}\in E\implies \forall i.\ \neg(v\in X_i\land w\in X_i)$

### Discussion

The $X_i$ are the partitions of the graph and the condition says that there can be no edge within an $X_i$, i.e. there are only connection from one partition to another. One can also few the partitions as different coloring of their vertices.

#### Theorems

From any $v\in X_i$, there can be edges to only the other partitions, i.e. to at most $|V|-|X_i|$ different other vertices. If we sum up the edges for all partitions and divide the double-counting out, we find that for an $k$-partite graph

$|E|\le \frac{1}{2}\sum_{i=1}^k |X_i|\cdot (|V|-|X_i|)$