I cannot understand last part of theorem 3., 2nd proof!
Theorem 3. Suppose $G$ is a graph on $n$ vertices without triangles. Then $G$ has at most $(n^2)/4$ edges, and equality holds only when n is even and $G$ is the complete bipartite graph $Kn/2$,$n/2$.
Second proof. The following proof of Theorem 3., using the inequality of the arithmetic and the geometric mean, is a folklore Book Proof. Let α be the size of a largest independent set A, and set $β = n − α$. Since $G$ is triangle-free, the neighbors of a vertex i form an independent set, and we infer $di ≤ α$ for all $i$.
The set $B = V \A$ of size $β$ meets every edge of $G$. Counting the edges of G according to their end vertices in $B$, we obtain $|E| ≤ i∈B di$. The inequality of the arithmetic and geometric mean now yields $|E| ≤ sigma di ≤ αβ ≤ (α + β)^ 2 = (n^2)/4 $ and again the case of equality is easily dealt with.
Can you explain it very easily?
I think if we reword it like this it is better:
Let $\Delta$ be the largest degree in the graph.
Take a vertex $v$ of degree $\Delta$, let $X$ be the neighbours of $v$. Notice every edge must have an endpoint outside $X$, so the number of edges is at most $\Delta(n-\Delta)$ (the sum of the degrees of vertices not in $X$ is at most this).
The function $f(x)=x(n-x)$ is easily shown to be maximized when $x=n/2$, you can so so with $AM-GM$, intelligent factorization or just plain calculus.