[proofplan] We upgrade an arbitrary $K_{r+1}$-free graph to a complete multipartite graph without decreasing its edge count by iterating a symmetrisation operation $T$ that replaces a "lighter" vertex with a clone of a "heavier" one. We assign rationally independent positive weights $\alpha_1, \ldots, \alpha_n$ to the vertices, define a weight $\mu(S) = \sum_{i \in S} \alpha_i$ on subsets, and use it as a tiebreaker to show the process is well-defined. The key properties are: (i) $T$ preserves $K_{r+1}$-freeness; (ii) $T$ does not decrease the edge count; (iii) the iteration stabilises (edge counts are bounded integers, and a secondary monovariant $\sum_x \mu(N(x))$ is also monotone). At the fixed point, non-adjacency is an equivalence relation, so the graph is complete multipartite with at most $r$ parts (else it would contain $K_{r+1}$). The edge bound $e(G) \leq e(T_{r,n})$ then follows from [Turán Graphs Maximise Edges Among $r$-Partite Graphs](/theorems/2042). [/proofplan] [step:Assign rationally independent weights and define the weight function on subsets] Fix $r \geq 2$ and let $G$ be a $K_{r+1}$-free graph on $n$ vertices. Enumerate the vertices as $v_1, \ldots, v_n$ and choose positive real numbers $\alpha_1, \ldots, \alpha_n \in \mathbb{R}_{>0}$ that are rationally independent (for example, $\alpha_i = \pi^i$). Define the weight function \begin{align*} \mu : 2^{V(G)} &\to \mathbb{R}_{\geq 0} \\ S &\mapsto \sum_{i : v_i \in S} \alpha_i. \end{align*} Rational independence ensures: if $S, S' \subseteq V(G)$ with $\mu(S) = \mu(S')$, then $S = S'$. In particular, distinct subsets have distinct weights. [guided] The reason for introducing weights is purely technical: we will define an operation $T$ that breaks ties by comparing neighbourhood weights, and we must guarantee unique tiebreaking. Rational independence of $\{\alpha_i\}$ means the only rational linear combination $\sum c_i \alpha_i = 0$ with $c_i \in \mathbb{Q}$ has all $c_i = 0$. Why does this force distinct weights? If $S \neq S'$ and $\mu(S) = \mu(S')$, then $\sum_{v_i \in S \triangle S'} \varepsilon_i \alpha_i = 0$ where $\varepsilon_i = \pm 1$ depending on which symmetric difference side $v_i$ lies in, contradicting rational independence. A concrete choice is $\alpha_i = \pi^i$: the $\alpha_i$ are rationally independent by the transcendence of $\pi$. This weight will order the $2^n$ subsets of $V(G)$ linearly, and we use that linear order as a tiebreaker to make the transformation $T$ unambiguous. [/guided] [/step] [step:Define the symmetrisation transformation $T$ and verify it preserves $K_{r+1}$-freeness] For a graph $H$ on $V(G)$, call an ordered pair $(x, y)$ of vertices of $H$ a **candidate pair** if: \begin{align*} \text{(i)} \quad N_H(x) &\neq N_H(y), \\ \text{(ii)} \quad x &\not\sim_H y, \\ \text{(iii)} \quad \text{either } \deg_H(x) > \deg_H(y), \text{ or } \deg_H(x) &= \deg_H(y) \text{ and } \mu(N_H(x)) > \mu(N_H(y)). \end{align*} Among all candidate pairs, pick the one maximising $\mu(\{x, y\})$ (unique by rational independence of the weights). Let $T(H)$ be the graph obtained by removing all edges incident to $y$ and adding an edge $yz$ for every $z \in N_H(x)$ — i.e. replacing $N_H(y)$ by $N_H(x)$. If no candidate pair exists, set $T(H) = H$. Note that the operation only modifies edges at $y$; the vertex set is unchanged. After the operation, $N_{T(H)}(y) = N_H(x)$ and in particular $y \notin N_H(x)$ (since $x \not\sim_H y$), so the redefinition is consistent (no self-loop). We claim that if $H$ is $K_{r+1}$-free, then so is $T(H)$. Suppose for contradiction that $T(H)$ contains a $K_{r+1}$ on vertex set $W \subseteq V$. If $y \notin W$, then all edges of the $K_{r+1}$ lie in $H$ too (since $T$ only modifies edges at $y$), contradicting $K_{r+1}$-freeness of $H$. So $y \in W$. Consider the set $W' = (W \setminus \{y\}) \cup \{x\}$: since $x \not\sim_H y$, $x \notin W$, and $|W'| = r + 1$. For each $w \in W \setminus \{y\}$, $w \in N_{T(H)}(y) = N_H(x)$ so $w \sim_H x$. And for any two distinct $w_1, w_2 \in W \setminus \{y\}$, the edge $w_1 w_2$ appears in $T(H)$ (since they are in the $K_{r+1}$ on $W$) and, because $y \notin \{w_1, w_2\}$, it also appears in $H$ (edges away from $y$ are preserved). Hence $W'$ spans a $K_{r+1}$ in $H$ — contradiction. [guided] The operation $T$ is a **symmetrisation**: we force the "lighter" vertex $y$ to be a clone of the "heavier" vertex $x$. The conditions on candidate pairs ensure we only replace when doing so is beneficial (more edges) and does not collapse anything (distinct neighbourhoods). The weight-maximisation in the choice of pair makes $T$ deterministic. **Why does $T$ preserve $K_{r+1}$-freeness?** The point is that $y$ and $x$ are **non-adjacent** in $H$. If $T(H)$ contained a $(r+1)$-clique $W$, then either: - $y \notin W$: all edges of the clique are inherited from $H$ (the only edges that change are those incident to $y$), so $H$ already has a $K_{r+1}$ — contradiction. - $y \in W$: each vertex $w \in W \setminus \{y\}$ satisfies $w \sim_{T(H)} y$, and by definition of $T$, $N_{T(H)}(y) = N_H(x)$, so $w \sim_H x$ for every such $w$. The vertices in $W \setminus \{y\}$ are pairwise adjacent in $T(H)$, and since they are distinct from $y$, their pairwise edges live in $H$ too (they are unaffected by $T$). Replacing $y$ with $x$ therefore gives a set $W' = (W \setminus \{y\}) \cup \{x\}$ of $r + 1$ distinct vertices (distinct because $x \not\sim_H y$ forces $x \neq y$, and $x \in N_H(x)^c$ gives $x \notin W \setminus \{y\}$) that span a $K_{r+1}$ in $H$ — contradicting $K_{r+1}$-freeness of $H$. So $T$ preserves $K_{r+1}$-freeness. This is precisely why we insist on the candidate condition (ii): non-adjacency is exactly what lets us "lift" a clique through $x$. [/guided] [/step] [step:Show $T$ is non-decreasing on edges and construct a secondary strict monovariant] We claim $e(T(H)) \geq e(H)$. Computing the edge change: the transformation replaces the $\deg_H(y)$ edges at $y$ by the $\deg_H(x)$ edges of a copy of $N_H(x)$ at $y$. (Since $x \not\sim_H y$ and no self-loop results, this is well-defined.) Hence \begin{align*} e(T(H)) - e(H) \;=\; \deg_H(x) - \deg_H(y). \end{align*} By the candidate condition (iii), $\deg_H(x) \geq \deg_H(y)$, so $e(T(H)) \geq e(H)$. When equality holds (i.e. $\deg_H(x) = \deg_H(y)$), the secondary tiebreaker in (iii) requires $\mu(N_H(x)) > \mu(N_H(y))$. The sum $\Psi(H) := \sum_{v \in V} \mu(N_H(v))$ then strictly increases at $y$: \begin{align*} \Psi(T(H)) - \Psi(H) \;=\; \mu(N_{T(H)}(y)) - \mu(N_H(y)) + \text{(contributions from other vertices)}. \end{align*} We verify the "other vertices" contribution is non-negative. For $v \neq y$, $N_{T(H)}(v) = N_H(v)$ except that $y$ may or may not be in this set. Specifically: $y \in N_{T(H)}(v)$ iff $v \in N_{T(H)}(y) = N_H(x)$. Thus $\mu(N_{T(H)}(v)) - \mu(N_H(v)) = \alpha_y \cdot [\mathbb{1}_{v \in N_H(x)} - \mathbb{1}_{v \in N_H(y)}]$. Summing over $v \neq y$: \begin{align*} \sum_{v \neq y} \bigl( \mu(N_{T(H)}(v)) - \mu(N_H(v)) \bigr) \;=\; \alpha_y \bigl( |N_H(x)| - |N_H(y)| \bigr) \;=\; \alpha_y \bigl( \deg_H(x) - \deg_H(y) \bigr) \;\geq\; 0. \end{align*} Combining with $\mu(N_{T(H)}(y)) = \mu(N_H(x)) > \mu(N_H(y))$ (when degrees match), we see that $\Psi$ strictly increases whenever $T$ acts non-trivially. [/step] [step:Conclude the iteration stabilises at some graph $G_\infty$] Define $G_0 := G$ and $G_{k+1} := T(G_k)$. The edge counts $e(G_k)$ form a non-decreasing integer sequence bounded above by $\binom{n}{2}$, so they stabilise: there exists $K_0$ with $e(G_k) = e(G_{K_0})$ for all $k \geq K_0$. After this, each application of $T$ preserves the edge count. From the previous step, $\Psi(G_k)$ then becomes a strictly increasing sequence (while $T$ acts non-trivially). Since $\Psi$ takes values in a finite set (namely $\{ \mu(S_1) + \cdots + \mu(S_n) : S_1, \ldots, S_n \subseteq V(G) \}$, a finite subset of $\mathbb{R}$), the sequence $\Psi(G_k)$ must also eventually stabilise. But $\Psi$ strictly increases when $T$ acts non-trivially, so after enough iterations $T$ must act as the identity. Let $G_\infty$ be any graph $G_{k^*}$ with $T(G_\infty) = G_\infty$; we have $e(G) \leq e(G_\infty)$. [guided] We iterate $T$ and want to prove the sequence stabilises at a fixed point. The standard monovariant argument uses two nested bounded monotone sequences: 1. **Primary monovariant: edge count** $e(G_k)$. This is a non-decreasing sequence of integers bounded by $\binom{n}{2}$, so it stabilises. 2. **Secondary monovariant: $\Psi(G_k) = \sum_{v} \mu(N_{G_k}(v))$.** After the edge count stabilises, every further application of $T$ must fall into the tiebreaker case (equal degrees, strictly larger $\mu(N(x))$ than $\mu(N(y))$), and in that case $\Psi$ strictly increases (as computed). Since $\Psi$ takes values in the finite set $\{ \sum_i \mu(S_i) : S_i \subseteq V \}$ (bounded by $n \cdot \mu(V)$ and confined to the finite lattice of achievable values, since the neighbourhoods are subsets of $V$ and there are $2^n$ such subsets), a strictly increasing sequence in $\Psi$ can have only finitely many terms. Hence $T$ must eventually act as the identity, giving a fixed point $G_\infty = T(G_\infty)$ with $e(G) \leq e(G_\infty)$ and $G_\infty$ still $K_{r+1}$-free. [/guided] [/step] [step:Show the fixed point is complete multipartite with at most $r$ parts] At the fixed point $G_\infty$, no candidate pair exists. We claim that non-adjacency in $G_\infty$ is an equivalence relation on $V(G_\infty)$. **Reflexivity** (by convention, $x \not\sim x$ as $G$ has no loops): holds. **Symmetry**: holds since the graph is undirected. **Transitivity**: let $x \not\sim y$ and $y \not\sim z$ with $x, y, z$ distinct. We must show $x \not\sim z$. We argue $N(x) = N(y) = N(z)$. Since no candidate pair exists, any two non-adjacent vertices $u, v$ with $N(u) \neq N(v)$ would produce one. Hence for every pair of non-adjacent vertices $u \not\sim v$ in $G_\infty$, we must have $N(u) = N(v)$ (otherwise one direction of the asymmetric condition in (iii) would produce a candidate pair $(u, v)$ or $(v, u)$, using the weight tiebreaker). Applying this to $x \not\sim y$ gives $N(x) = N(y)$, and to $y \not\sim z$ gives $N(y) = N(z)$, hence $N(x) = N(z)$. Now $x \in N(x)$ is impossible (no loops), and $x \notin N(z) = N(x)$ shows $x \not\sim z$. So non-adjacency is transitive. Hence non-adjacency partitions $V(G_\infty)$ into equivalence classes $C_1, \ldots, C_k$: vertices in the same class are pairwise non-adjacent, and vertices in different classes are adjacent. In other words, $G_\infty = K_{|C_1|, \ldots, |C_k|}$ is a complete $k$-partite graph. Since $G_\infty$ is $K_{r+1}$-free and a complete $k$-partite graph contains a $K_k$ (by picking one vertex from each part), we must have $k \leq r$. [guided] The fixed-point condition "no candidate pair" translates into a strong structural statement: non-adjacency is an equivalence relation. Let us see why. Let $u \not\sim v$ in $G_\infty$ with $u \neq v$. If $N(u) \neq N(v)$, then one of the asymmetric conditions in (iii) holds — either degrees differ, or they match and $\mu(N(u)) \neq \mu(N(v))$ (since $N(u) \neq N(v)$ and rational independence gives $\mu(N(u)) \neq \mu(N(v))$). Either way, $(u, v)$ or $(v, u)$ is a candidate pair, contradicting the fixed-point property. So $N(u) = N(v)$ whenever $u \not\sim v$. **Transitivity**: if $x \not\sim y$ and $y \not\sim z$ with $x \neq z$, then $N(x) = N(y) = N(z)$. Since $x \notin N(x)$ (no loops), $x \notin N(z)$ too, i.e. $x \not\sim z$. So the complement of the adjacency relation is an equivalence relation (modulo reflexivity, which is trivial in simple graphs). The equivalence classes are **independent sets** (by definition, non-adjacency), and any two vertices in **different** classes are adjacent (they would be non-adjacent otherwise, forcing them into the same class). This is precisely the definition of a complete $k$-partite graph where $k$ is the number of classes. Since $G_\infty$ is complete $k$-partite, it contains $K_k$ (take one vertex from each class). The $K_{r+1}$-freeness forces $k \leq r$. [/guided] [/step] [step:Conclude using the Turán-graph optimality among $r$-partite graphs] $G_\infty$ is a complete $k$-partite graph with $k \leq r$. A complete $k$-partite graph is also $r$-partite (refine each part into one non-empty and $r - k$ empty sub-parts — or equivalently, any $k$-partite graph is $r$-partite whenever $k \leq r$). By [Turán Graphs Maximise Edges Among $r$-Partite Graphs](/theorems/2042), \begin{align*} e(G_\infty) \;\leq\; e(T_{r, n}). \end{align*} Combined with $e(G) \leq e(G_\infty)$ from Step 4, \begin{align*} e(G) \;\leq\; e(T_{r, n}), \end{align*} which is the desired bound. [/step]