Let $G$ be a simple graph with $n$ vertices. Show that if $G$ has no triangles (cycles of length 3), then the number of edges in $G$ is at most $\lfloor n^2/4\rfloor$.

Step 1: Let the vertices of the graph be $V=\{v_1,v_2,\dots ,v_n\}$. Let $d(v_i)$ represent the degree of vertex $v_i$, and $E$ be the set of edges.

Step 2: Since the graph contains no triangles, for any two connected vertices $x$ and $y$ (i.e. $xy\in E$), they cannot share any common neighbors. Therefore, the sum of their degrees must satisfy:

Step 3: Summing this inequality over all edges $xy\in E$:

Step 4: Note that in the sum on the left, each vertex $v$ appears exactly $d(v)$ times (once for each edge it is connected to). Thus:

Step 5: By the Cauchy-Schwarz inequality, we have:

Step 6: Combining these inequalities:

Since $|E|$ must be an integer, $|E|\le \lfloor n^2/4\rfloor$. This completes the proof of Mantel's Theorem.