Graph theory - inequality I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory.
We consider G = (V,E) a graph with n a natural number (n is the number of vertices), that doesn't contain any triangles. (so the vertices don't form any triangle inside the graph)
the problem is about solving :   |E|≤ (n^2) / 4
all I know is that {u,v}∈E : deg(u)+deg(v) ≤ n
(I don't know if it is relevant to the problem though...)
 A: Recall by the Cauchy-Schwarz inequality that if $\vec a, \vec b \in \mathbb R^n$, then $\vec a \cdot \vec b \leq \|\vec a\|  \|\vec b\|$, which can be rewritten as:
$$
\left(\sum_{i=1}^n a_ib_i \right)^2 \leq \left(\sum_{i=1}^n a_i^2 \right)\left(\sum_{i=1}^n b_i^2 \right)
$$
Now let $V = \{v_1, \ldots, v_n\}$ and take $a_i = 1$ and $b_i = \deg v_i$.
Then it follows that:
\begin{align*}
|E|
&= \frac{(2|E|)^2}{4|E|} \\
&= \frac{\left(\sum_{i=1}^n 1\deg v_i \right)^2}{4|E|} &\text{by the handshaking lemma}\\
&\leq \frac{\left(\sum_{i=1}^n 1^2 \right)\left(\sum_{i=1}^n (\deg v_i)^2 \right)}{4|E|} &\text{by the Cauchy-Schwarz inequality}\\
&= \frac{n\sum_{i=1}^n\sum_{v_iv_j \in E} (\deg v_i) }{4|E|} \\
&= \frac{n\sum_{v_iv_j \in E} (\deg v_i + \deg v_j)}{4|E|} \\
&\leq \frac{n(n|E|)}{4|E|} &\text{since $G$ is triangle-free}\\
&= \frac{n^2}{4}
\end{align*}
as desired. $~~\blacksquare$
A: Here's another approach:
Let $v$ be a vertex of maximum degree in $G=(V,E)$.  Then $$\mathrm{deg}(v) \geq \text{ave. deg.} = \dfrac{2|E|}{n} \geq \dfrac{n}{2}$$ since $|E| \leq n^2/4$.
Let $S$ be the set of neighbors of $v$.  Let $H$ be the complete bipartite graph with vertex bipartition formed by $S$ and $V \setminus S$.
We observe:


*

*$H$ has at most $n^2/4$ edges,

*in going from $G$ to $H$,


*

*the degree of $v$ remains the same,

*the degrees of the vertices in $S$ are no smaller in $H$ than in $G$, and

*the degrees of the vertices in $V \setminus ( S \cup \{v\} )$ are now all equal to $|S|=\mathrm{deg}(v)$, which is the maximum degree in $G$,


so $H$ has no fewer edges than $G$, and

*$H$ is triangle free.
Hence $|E| \leq n^2/4$.
