Editing Turán's theorem (section)

=== Zykov Symmetrization ===
Aigner and Ziegler call the final one of their five proofs "the most beautiful of them all". Its origins are unclear, but the approach is often referred to as Zykov Symmetrization as it was used in Zykov's proof of a generalization of Turán's Theorem {{r|zykov}}. This proof goes by taking a <math>K_{r+1}</math>-free graph, and applying steps to make it more similar to the Turán Graph while increasing edge count.

In particular, given a <math>K_{r+1}</math>-free graph, the following steps are applied:

* If <math>u,v</math> are non-adjacent vertices and <math>u</math> has a higher degree than <math>v</math>, replace <math>v</math> with a copy of <math>u</math>. Repeat this until all non-adjacent vertices have the same degree.
* If <math>u,v,w</math> are vertices with <math>u,v</math> and <math>v,w
</math> non-adjacent but <math>u,w</math> adjacent, then replace both <math>u</math> and <math>w
</math> with copies of <math>v
</math>.

All of these steps keep the graph <math>K_{r+1}</math> free while increasing the number of edges.

Now, non-adjacency forms an [[equivalence relation]]. The [[equivalence class]]es give that any maximal graph the same form as a Turán graph. As in the maximal degree vertex proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.{{r|az}}