An interesting proof of Turán’s theorem
In the past few days I have been reading a nice book about graph theory, including solving the exercises in it. Once I encountered an exercise which I couldn’t solve, so made a little research, and found that the solution is the proof of the Turán’s theorem.
The usual proof for this theorem is built on induction, but later I have found a proof which is using a basic inequality.
I am sure that I’m not the first one who have seen this solution, although I couldn’t find it on the net yet.
Used variables:
- n: number of vertices
- m: number of edges
- k: number of partitions over the vertices
- ai:number of vertices inside partition i
All are natural numbers
The sum of the vertices inside the partitions gives the full number of vertices. We will use this many times.
The number of edges in a complete k-parted graph is:
We can formulate (2) to a form which contains sum of squares, using (1).
Now let’s write down the inequality between the arithmetic and the quadratic mean, over the partitions. This inequality can be derived from the Cauchy-Schwarz inequality.
Again (1) is used, and at the end we made the quadratic sum explicit on the right side.
Before I found this, I was thinking a lot how to connect the sum of squares of the partitions – which can be found in (3) – to a constant in a way which would give us a lower limit, and an equality when the partitions have equal sizes. We need a lower limit because the quadratic sum in (3) is after a minus sign, and we need a maximum for m.
Now we only have to multiply (4) with -1, then add n^2 and after that, divide by 2, and we get an upper bound for the number of edges, because now the left side equals to m. (see (3).)
There is equality in (5) in the case the partitions have equal number of vertices. This is because the “inequality between the arithmetic and the quadratic mean” has this property.
Although the equality of the partitions is only possible when k|n, in other cases they can be only nearly equal. On the one hand this can be interpreted as a flaw of the proof, but on the other hand, it also suggests that the inequality between the arithmetic and the quadratic mean also has this sensitivity to “nearly equal” values, which could lead to other investigations.
