From "A Brief Introduction to Spectral Graph Theory" Exercise 1.2 states
A graph on $n$ vertices that contains no 3-cycles has at most $\lfloor \frac{n^2}{4}\rfloor$ edges.
My thought process was to suppose otherwise. Then by the Handshaking Lemma:
$$\sum_{v \in V} \deg(v) = 2|E| > 2\left\lfloor\frac{n^2}{4}\right\rfloor = \frac{n^2}{2}$$
Furthermore, as there are $n$ vertices:
$$\frac{\sum_{v \in V} \deg(v)}{n} > \frac{n}{2}$$
Thus, the average degree is $> n/2$. From here I am stuck. I thought an avenue of approach would be to consider a vertex $v$ with maximal degree. $v$ must be connected to over half of the vertices. Furthermore, none of its neighbors can be connected (otherwise there would be a $3$-cycle) but I am not exactly sure how to continue this line of reasoning. Any hints would be appreciated.
Best Answer
Though I agree with Misha Lavrov that this is a deceivingly placed exercise, you can come up with a proof using ideas you have outlined, together with an application of the AM-GM inequality: for non-negative reals $x$ and $y$, $\sqrt{xy}\leq \frac{x+y}{2}$.
Let $G$ be a graph with no $3$-cycle. We show $G$ has at most $\lfloor\frac{n^2}{4}\rfloor$ edges. As you have observed, no two neighbours of a vertex are adjacent, i.e., the neighbourhood of any vertex is an independent set. Moreover, the size of a largest independent set is thus an upper bound on the degree of a vertex in $G$. Let $I$ be a largest independent set in $G$, and let $J=V(G)\backslash I$. By the handshaking lemma
$$ 2|E(G)|=\sum_{v\in V(G)}\deg(v) = \sum_{v\in I}\deg(v)+\sum_{v\in J}\deg(v). $$
Now, every edge with one end in $I$ has its other end in $J$. Thus
$$ \sum_{v\in I}\deg(v)\leq \sum_{v\in J}\deg(v) , $$ so $$ |E(G)|\leq \sum_{v\in J}\deg(v) \leq |J||I|, $$ where we use the previously established bound $d(v)\leq |I|$. Finally, using the AM-GM inequality,
$$ |J||I|\leq \frac{(|J|+|I|)^2}{4} = \frac{n^2}{4}, $$ so $|E(G)|\leq \frac{n^2}{4}$, and since the number of edges of a graph is an integer, $|E(G)|\leq \lfloor\frac{n^2}{4}\rfloor$, as desired.