Complete multipartite graph

A complete multipartite graph partitions its vertices into independent sets and joins every pair of vertices from different parts.

The octahedral graph is the graph obtained from

K_{6}

by removing a perfect matching; equivalently it is

K_{2, 2, 2}

. Its chromatic number is three, and it contains two vertex-disjoint triangles in a graph. A complete bipartite graph with a single additional internal edge cannot contain it: every triangle in that host uses the additional edge.

Balancing a multipartite edge-triangle objective ( $F = \sum_{i < j} a_{i} a_{j} - c \sum_{i < j < k} a_{i} a_{j} a_{k}$ )

 0  0

With two part sizes of fixed sum and all other sizes fixed, this objective has form constant plus

(1 - c B) a_{i} a_{j}

, where

B

is the sum of the other sizes. A nonpositive coefficient permits merging the pair, while a positive coefficient favours balancing it. Choose an optimum with fewest nonzero parts: all remaining coefficients are positive, and the integer sizes differ by at most one. For real sizes they are exactly equal. This explains extremizers among Turán graphs.