[proofplan] We argue by contradiction via an extremal choice. Among all $r$-partite graphs on $n$ vertices with the maximum number of edges, pick one and call it $G$. Two observations force $G$ to be the Turán graph $T_{r, n}$: first, $G$ must be the **complete** $r$-partite graph with its part sizes (any missing cross-part edge could be added without destroying $r$-partiteness, contradicting maximality); second, the part sizes must be as balanced as possible, i.e. differ by at most one. Unbalancedness is ruled out by a local swap — moving one vertex from a larger part to a smaller part strictly increases the edge count because the vertex gains more new neighbours in the enlarged remainder of its old part than it loses in the new part. The resulting structure is isomorphic to $T_{r, n}$ by uniqueness of the balanced complete multipartite graph. [/proofplan] [step:Extract an extremal $r$-partite graph on $n$ vertices] Let $\mathcal{G}$ be the set of all $r$-partite graphs on $n$ vertices. The set $\mathcal{G}$ is non-empty (e.g. the edgeless graph is $r$-partite) and the edge counts $\{ e(G) : G \in \mathcal{G} \}$ form a bounded non-empty subset of $\mathbb{Z}_{\geq 0}$ (bounded above by $\binom{n}{2}$). Hence the maximum is attained: choose $G \in \mathcal{G}$ with $e(G) = \max_{G' \in \mathcal{G}} e(G')$. Fix an $r$-partition $V(G) = V_1 \sqcup \cdots \sqcup V_r$ witnessing that $G$ is $r$-partite (i.e. each $V_i$ is an independent set in $G$), and write $n_i = |V_i|$ with $\sum_i n_i = n$. Some $n_i$ may be zero. [guided] We work by contradiction via extremality: assume for contradiction there is an $r$-partite graph with more edges than $T_{r, n}$, then derive a contradiction from a maximiser. The existence of a maximiser is a finiteness argument — there are finitely many graphs on $n$ labelled vertices, hence finitely many $r$-partite ones, hence the edge count attains its maximum. Why fix the partition explicitly? $r$-partiteness is a property of the abstract graph but the specific witnessing partition is extra data. Many of our arguments (moving a vertex between parts, adding cross-part edges) require pinning down the partition. [/guided] [/step] [step:Show $G$ is the complete $r$-partite graph on its part sizes] We claim $G = K_{n_1, \ldots, n_r}$, the complete $r$-partite graph with the given part sizes. Suppose not: then there exist $u \in V_i$ and $w \in V_j$ with $i \neq j$ and $uw \notin E(G)$. Define $G^+ := G + uw$ (the graph obtained by adding the edge $uw$). $G^+$ is $r$-partite, witnessed by the same partition $V_1 \sqcup \cdots \sqcup V_r$: the only new edge $uw$ goes between parts $V_i$ and $V_j$ with $i \neq j$, so each $V_\ell$ remains an independent set. Hence $G^+ \in \mathcal{G}$. But $e(G^+) = e(G) + 1 > e(G)$, contradicting the maximality of $G$. Therefore every pair of vertices in different parts is adjacent, i.e. $G = K_{n_1, \ldots, n_r}$. [/step] [step:Balance the parts: show $|n_i - n_j| \leq 1$ for all $i, j$] Suppose for contradiction that some pair of parts $V_i, V_j$ has part sizes differing by at least $2$; after relabelling, assume $n_i \geq n_j + 2$. Pick any vertex $v \in V_i$ and let $G'$ be the graph obtained by moving $v$ from $V_i$ to $V_j$: the new partition is $V_1 \sqcup \cdots \sqcup (V_i \setminus \{v\}) \sqcup \cdots \sqcup (V_j \cup \{v\}) \sqcup \cdots \sqcup V_r$, and we let $G'$ be the **complete** $r$-partite graph on this partition. $G'$ is $r$-partite (by construction), so $G' \in \mathcal{G}$. We compute the edge count change. Under the move, the edges incident to $v$ change as follows: - **Lost**: in $G$, $v$ is adjacent to every vertex outside $V_i$, i.e. $v$ had $n - n_i$ neighbours. In $G'$, $v$ (now in $V_j \cup \{v\}$) is adjacent to every vertex outside $V_j \cup \{v\}$, i.e. $v$ now has $n - n_j - 1$ neighbours. So edges at $v$: gained $(n - n_j - 1) - (n - n_i) = n_i - n_j - 1$. - **Edges not incident to $v$**: all other cross-part pairs remain cross-part pairs in the new partition (moving $v$ only affects whether a pair involves $v$), so those edges are unchanged. Therefore \begin{align*} e(G') - e(G) \;=\; (n_i - n_j - 1) \;\geq\; (n_j + 2) - n_j - 1 \;=\; 1 \;>\; 0. \end{align*} This contradicts the maximality of $G$ in $\mathcal{G}$. Hence $|n_i - n_j| \leq 1$ for all $i, j$. [guided] The key calculation is the edge-count change when a single vertex is moved between parts. Let us redo it carefully. **Setup.** $G = K_{n_1, \ldots, n_r}$ with $n_i \geq n_j + 2$. Pick $v \in V_i$. Move $v$ to part $V_j$: new part sizes are $n_i' = n_i - 1$ and $n_j' = n_j + 1$, with all other $n_\ell' = n_\ell$. Let $G'$ be the complete $r$-partite graph on the new partition. **In $G$** (before the move): $v \in V_i$ is adjacent to every vertex outside $V_i$, which is $n - n_i$ vertices. All other edges of $G$ are unchanged. **In $G'$** (after the move): $v$ is in the new $V_j$ part of size $n_j + 1$. It is adjacent to every vertex outside this new part, which is $n - (n_j + 1) = n - n_j - 1$ vertices. All edges of $G'$ not incident to $v$ are the same as the corresponding edges of $G$ not incident to $v$ (both graphs are complete multipartite with their respective partitions, and a pair of non-$v$ vertices is cross-partition in $G$ iff it is cross-partition in $G'$, since the move only reassigns $v$). Hence \begin{align*} e(G') - e(G) \;=\; \deg_{G'}(v) - \deg_G(v) \;=\; (n - n_j - 1) - (n - n_i) \;=\; n_i - n_j - 1. \end{align*} Under the assumption $n_i \geq n_j + 2$ this is $\geq 1$, so $e(G') > e(G)$, contradicting extremality. In prose: moving $v$ to the smaller part causes $v$ to keep all its edges except those to $V_j$ (of which there were $n_j$), and to gain new edges to the old $V_i \setminus \{v\}$ (of which there are $n_i - 1$). The net change is $(n_i - 1) - n_j = n_i - n_j - 1$, positive when $n_i - n_j \geq 2$. [/guided] [/step] [step:Conclude $G \cong T_{r, n}$] We now know $G$ is the complete $r$-partite graph $K_{n_1, \ldots, n_r}$ with $\sum_i n_i = n$ and $|n_i - n_j| \leq 1$ for all $i, j$. The condition $|n_i - n_j| \leq 1$ with $\sum n_i = n$ determines the part sizes uniquely up to permutation: there are two values, $\lceil n/r \rceil$ and $\lfloor n/r \rfloor$, and $n \bmod r$ parts of size $\lceil n/r \rceil$ and $r - (n \bmod r)$ parts of size $\lfloor n/r \rfloor$. This is exactly the definition of the Turán graph $T_{r, n}$. Hence $G \cong T_{r, n}$ and $e(G) = e(T_{r, n})$. Since $G$ was the maximum-edge $r$-partite graph, every $r$-partite graph on $n$ vertices satisfies $e(G') \leq e(G) = e(T_{r, n})$, which completes the proof. [guided] The part-size balancing condition $|n_i - n_j| \leq 1$ is equivalent to saying the part sizes take at most two values, which must be consecutive integers. Let $a = \lfloor n / r \rfloor$ and $s = n - ra \in \{0, 1, \ldots, r-1\}$. Then exactly $s$ parts have size $a + 1$ and $r - s$ parts have size $a$: \begin{align*} \sum_i n_i \;=\; s(a + 1) + (r - s) a \;=\; ra + s \;=\; n. \;\checkmark \end{align*} The Turán graph $T_{r, n}$ is by definition the complete $r$-partite graph with these part sizes, so $G \cong T_{r, n}$ as unlabelled graphs, hence $e(G) = e(T_{r, n})$. Since $G$ was chosen to maximise $e$ over $\mathcal{G}$, for any $r$-partite graph $G' \in \mathcal{G}$ on $n$ vertices, \begin{align*} e(G') \;\leq\; e(G) \;=\; e(T_{r, n}). \end{align*} This establishes the theorem. [/guided] [/step]