k-partite graph
Set
| context | k∈N |
| context | V … set |
| definiendum | ⟨V,E⟩∈it(E,V) |
| inclusion | ⟨V,E⟩ … undirected graph |
| range | i,j∈{1,…,k} |
| range | ⋃iXi=V |
| range | ∀i,j. Xi∩Xj=∅ |
| range | v,w∈V |
| postulate | ∃X1,…,Xk. ∀u,v. {u,v}∈E⟹∀i. ¬(v∈Xi∧w∈Xi) |
Discussion
The Xi are the partitions of the graph and the condition says that there can be no edge within an Xi, 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∈Xi, there can be edges to only the other partitions, i.e. to at most |V|−|Xi| 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|≤12∑ki=1|Xi|⋅(|V|−|Xi|)
Parents
Subset of
