[proofplan] We prove the contrapositive: if $G$ is triangle-free on $n$ vertices, then $e(G) \leq n^2/4$. The core observation is that for any edge $xy$ in a triangle-free graph, the neighbourhoods $N(x)$ and $N(y)$ are disjoint, so $\deg(x) + \deg(y) \leq n$. Summing this inequality over all edges converts the vertex-sum on the left into $\sum_x \deg(x)^2$, which we lower-bound by Jensen's inequality applied to the convex function $t \mapsto t^2$. Combining the two estimates yields a quadratic inequality in $e(G)$ from which $e(G) \leq n^2/4$ follows. [/proofplan] [step:Use triangle-freeness to bound $\deg(x) + \deg(y) \leq n$ for every edge $xy$] Suppose for contradiction that $G$ is a graph on $n$ vertices with $e(G) > n^2/4$ and $G$ is triangle-free. Let $xy$ be any edge of $G$. Since $G$ is triangle-free, no vertex $z$ is adjacent to both $x$ and $y$, so $N(x) \cap N(y) = \varnothing$. As $N(x), N(y) \subseteq V(G)$ and $|V(G)| = n$, \begin{align*} \deg(x) + \deg(y) \;=\; |N(x)| + |N(y)| \;=\; |N(x) \cup N(y)| \;\leq\; n. \end{align*} [guided] The contrapositive is cleaner: assume $G$ has no triangle and derive $e(G) \leq n^2/4$. The entire argument flows from a single structural consequence of triangle-freeness on an edge $xy$: **there is no vertex adjacent to both endpoints**. Let $xy \in E(G)$. If some vertex $z$ were adjacent to both $x$ and $y$, then the three vertices $x, y, z$ together with the edges $xy$, $xz$, $yz$ would form a triangle — contradicting our assumption. Hence $N(x) \cap N(y) = \varnothing$. The two neighbourhoods $N(x)$ and $N(y)$ are disjoint subsets of $V(G)$, so \begin{align*} \deg(x) + \deg(y) \;=\; |N(x)| + |N(y)| \;=\; |N(x) \cup N(y)| \;\leq\; |V(G)| \;=\; n. \end{align*} This local inequality — one per edge — is the entire combinatorial input of the proof. Everything that follows is a clean double-counting argument. [/guided] [/step] [step:Sum over edges to convert the bound into $\sum_x \deg(x)^2 \leq n \cdot e(G)$] Summing the inequality $\deg(x) + \deg(y) \leq n$ over all $e(G)$ edges $xy \in E(G)$: \begin{align*} \sum_{xy \in E(G)} \bigl( \deg(x) + \deg(y) \bigr) \;\leq\; n \cdot e(G). \end{align*} We evaluate the left-hand side by a double counting argument. Each vertex $x \in V(G)$ contributes the term $\deg(x)$ once for every edge incident to $x$, and there are $\deg(x)$ such edges. Hence the total contribution of $x$ to the sum is $\deg(x) \cdot \deg(x) = \deg(x)^2$, and \begin{align*} \sum_{xy \in E(G)} \bigl( \deg(x) + \deg(y) \bigr) \;=\; \sum_{x \in V(G)} \deg(x)^2. \end{align*} Therefore \begin{align*} \sum_{x \in V(G)} \deg(x)^2 \;\leq\; n \cdot e(G). \tag{$\ast$} \end{align*} [guided] We now aggregate the local per-edge bound into a global statement. Summing over all edges, \begin{align*} \sum_{xy \in E(G)} \bigl( \deg(x) + \deg(y) \bigr) \;\leq\; \sum_{xy \in E(G)} n \;=\; n \cdot e(G). \end{align*} The left-hand side looks asymmetric (a sum over edges of a vertex-symmetric expression), but it has a clean vertex-indexed form via double counting. Fix a vertex $x$. For which edges does $x$ contribute $\deg(x)$ to the sum? Precisely those edges where $x$ is one of the two endpoints — i.e. the $\deg(x)$ edges incident to $x$. Each such edge contributes one copy of $\deg(x)$. Hence $x$'s total contribution is $\deg(x) \cdot \deg(x) = \deg(x)^2$, and \begin{align*} \sum_{xy \in E(G)} \bigl( \deg(x) + \deg(y) \bigr) \;=\; \sum_{x \in V(G)} \deg(x)^2. \end{align*} Combining with the upper bound from summing the edge inequality, \begin{align*} \sum_{x \in V(G)} \deg(x)^2 \;\leq\; n \cdot e(G). \tag{$\ast$} \end{align*} This is the "sum-of-squares of degrees" inequality for triangle-free graphs. The next step extracts an estimate for $e(G)$ itself by lower-bounding the left-hand side via Jensen. [/guided] [/step] [step:Apply Jensen's inequality with $f(t) = t^2$ to lower-bound the degree-squared sum] The function $f: \mathbb{R} \to \mathbb{R}$, $t \mapsto t^2$ is convex (its second derivative is $f''(t) = 2 \geq 0$). By Jensen's inequality applied to the discrete uniform distribution on $V(G)$, \begin{align*} \frac{1}{n} \sum_{x \in V(G)} \deg(x)^2 \;\geq\; \left( \frac{1}{n} \sum_{x \in V(G)} \deg(x) \right)^2. \end{align*} The handshake lemma gives $\sum_{x \in V(G)} \deg(x) = 2 e(G)$. Substituting, \begin{align*} \sum_{x \in V(G)} \deg(x)^2 \;\geq\; n \cdot \left( \frac{2 e(G)}{n} \right)^2 \;=\; \frac{4 e(G)^2}{n}. \tag{$\ast\ast$} \end{align*} [/step] [step:Combine $(\ast)$ and $(\ast\ast)$ to conclude $e(G) \leq n^2/4$] Chaining $(\ast)$ and $(\ast\ast)$: \begin{align*} \frac{4 e(G)^2}{n} \;\leq\; \sum_{x \in V(G)} \deg(x)^2 \;\leq\; n \cdot e(G). \end{align*} Dividing both sides by $e(G)$ (valid if $e(G) > 0$; if $e(G) = 0$, the conclusion $e(G) \leq n^2/4$ holds immediately), \begin{align*} \frac{4 e(G)}{n} \;\leq\; n, \qquad \text{hence} \qquad e(G) \;\leq\; \frac{n^2}{4}. \end{align*} This contradicts the assumption $e(G) > n^2/4$. Therefore $G$ contains a triangle. [guided] We have two inequalities involving the same quantity $\sum_x \deg(x)^2$: \begin{align*} \frac{4 e(G)^2}{n} \;\leq\; \sum_{x \in V(G)} \deg(x)^2 \;\leq\; n \cdot e(G). \end{align*} The left bound (from Jensen) is a lower bound; the right bound (from triangle-freeness) is an upper bound. Sandwiching gives $\frac{4 e(G)^2}{n} \leq n \cdot e(G)$. If $e(G) = 0$, then $e(G) \leq n^2/4$ holds immediately and there is nothing to prove. Assume $e(G) > 0$. Dividing both sides by $e(G)$ (a legitimate positive quantity), \begin{align*} \frac{4 e(G)}{n} \;\leq\; n, \qquad \text{i.e.} \qquad e(G) \;\leq\; \frac{n^2}{4}. \end{align*} This contradicts the starting hypothesis $e(G) > n^2/4$. The contradiction shows that $G$ cannot be triangle-free, completing the proof. Note on sharpness: the bound is attained by the balanced complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$, which is triangle-free and has $\lfloor n^2/4 \rfloor$ edges. The Turán graph $T_{2,n}$ is the extremal example. [/guided] [/step]