5
$\begingroup$

I find two different formulations of Turán's theorem and I don't see why they are equivalent.

One is:

(1) Let $G$ be any graph with $n$ vertices, such that $G$ is $K_{r+1}$ -free. Then the number of edges in $G$ is at most

$$\frac{r-1}{r}.\frac{n^2}{2}$$

(for example from Wikipedia)

The other one is:

(2) If $G$ is a graph with $n$ vertices and $e$ edges then there is an independent set of size at least $$\frac{n}{\frac{2e}{n} + 1}$$

(for example from this document)

$\endgroup$

1 Answer 1

2
$\begingroup$

It seems the following.

Let $G'$ be the complement graph for $G$, $r$ be the maximal size of a clique of the graph $G$ (which is equal to the maximal size of an independent set of the graph $G'$), and $r'$ be the maximal size of a clique of the graph $G'$ (which is equal to the maximal size of an independent set of the graph $G$).

(1) $\Rightarrow$ (2). The graph $G'$ is $K_{r'+1}$ free and therefore $\frac{n(n-1)}2-e(G)=e(G')\le\frac{r'-1}{r'}\frac{n^2}{2}$. Simplifying the last inequality we obtain (2).

(2) $\Rightarrow$ (1). In this case $r\ge \frac{n^2}{2e(G') + n}= \frac{n^2}{n(n-1)-2e(G)+ n}$. Simplifying the last inequality we obtain (1).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .