LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The exact edge count of $T_{n, r}$ and the unique balancing maximum among complete $r$ -partite graphs

Statement

Let $r \geq 1$ and write $n = q r + a$ with $0 \leq a < r$ . Then

$e (T_{n, r}) = (\binom{n}{2}) - a (\binom{q + 1}{2}) - (r - a) (\binom{q}{2}) = \frac{1}{2} (n^{2} - a (q + 1)^{2} - (r - a) q^{2}) .$

Among complete $r$ -partite graphs on $n$ vertices, this is the maximum edge count. Equality holds exactly when all part sizes differ by at most $1$ , hence exactly for a graph isomorphic to $T_{n, r}$ . Also

$e (T_{n, r}) \leq \frac{r - 1}{2 r} n^{2},$

with equality exactly when $r$ divides $n$ .

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

For $n = q r + a$ , $T_{n, r}$ is the complete $r$ -partite graph with $a$ parts of size $q + 1$ and $r - a$ parts of size $q$ (Ordinary-subgraph extremal number $ex (n, H)$ , Turán graph $T_{n, r}$ , and balanced blowup $H [s]$ ).

[F2]

If $V$ has $n$ elements, the complete graph $K_{V}$ has exactly $(\binom{n}{2})$ edges (The complete graph on an $n$ -element vertex set has $(\binom{n}{2})$ edges).

[F3]

$(\binom{n}{k})$ is the number of $k$ -element subsets of an $n$ -element set (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Proof

technique · count missing within-part pairs and balance parts

1.1

A complete multipartite graph contains every vertex pair except pairs within one part. If its part sizes are $n_{1}, \dots, n_{r}$ , its edge count is $(\binom{n}{2}) - \sum_{i} (\binom{n_{i}}{2}) = \frac{1}{2} (n^{2} - \sum_{i} n_{i}^{2})$ . Substituting the $a$ sizes $q + 1$ and the remaining sizes $q$ gives both displayed exact formulas.

givenF1F2F3

2.1

If $n_{i} \geq n_{j} + 2$ , moving one vertex from part $i$ to part $j$ changes $\sum_{k} n_{k}^{2}$ by $(n_{i} - 1)^{2} + (n_{j} + 1)^{2} - n_{i}^{2} - n_{j}^{2} = - 2 (n_{i} - n_{j} - 1) < 0$ , so it strictly increases the edge count. Repetition ends exactly when every two part sizes differ by at most $1$ , which forces the quotient-remainder sizes and proves both maximality and uniqueness.

step 1.1

2.2

The identity $\sum_{i} (n_{i} - n / r)^{2} = \sum_{i} n_{i}^{2} - n^{2} / r \geq 0$ gives $e \leq (r - 1) n^{2} / (2 r)$ . Equality requires every $n_{i} = n / r$ , possible exactly when $r$ divides $n$ ; for the balanced integer sizes the converse is immediate.

step 1.1

3.1

Steps 1.1-2.2 prove the exact count, balancing characterization, quadratic bound, and both equality cases, including $n = 0$ and $r = 1$ .

step 1.1step 2.1step 2.2∎

Depends on

Used by

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)

The exact edge count of Tn,rTn,r​ and the unique balancing maximum among complete rr-partite graphs