|
Let $G$ be a triangle-free graph of order $n$ For each edge $xy$ of $G$ we consider the neighbourhoods $\Gamma(x)$ and $\Gamma(y)$ of $G$ Since $G$ is triangle-free, these are disjoint.
This is only possible if the sum of the degrees of $x$ and $y$ is less than or equal to $n$ So for each edge $xy$ we get the inequality
$$ \delta(x)+\delta(y)\leq n $$
Summing these inequalities for all edges of $G$ gives us $$ \Sigma_{x\in V(G)} (\delta(x))^2 \leq n |E(G)| $$
(The left hand side is a sum of $\delta(x)$ where each edge incident with $x$ contributes one term and their are $\delta(x)$ such edges.)
Since $\Sigma_{x\in V(G)} \delta(x) = 2 |E(G)|$ we get $4 |E(G)|^2 = (\Sigma_{x\in V(G)} \delta(x))^2 $ and applying the Cauchy-Schwarz inequality gives $4 |E(G)|^2 \leq n \Sigma_{x\in V(G)} (\delta(x))^2 \leq n^2 |E(G)|$
So we conclude that for a triangle-free graph $G$ $$|E(G)|\leq\frac{n^2}{4} $$
|