Prove that if the graph on $n$ vertices has at least $(n / 2)^2 + 1$ edges, then it has a triangle in it.

Question

Prove that if the graph on $n$ vertices has at least $(n/2)^2+1$ edges , then it has a triangle in it.

I know if edges are $(n/2)^2+1$ then sum of grades is $2(n/2)^2+2$ and I think I've to figure out how many vertecies have to have some grade for making triangle.

Answer 1

There are many proofs of Mantel's theorem. The following is how I usually think of it:

Let $G$ be a graph without triangles and $e(G)$ maximum. If there are two vertices that are not adjacent, $v$ and $w$, and $deg(v)>deg(w)$, delete $w$, and replace it with an identical copy of $v$ (i.e. they have the same neighborhood). In particular, $v$ and its copy are non-adjacent, so the resulting graph would still be triangle free, and have more edges. So we may assume $deg(v)=deg(w)$ for all non-adjacent vertices.

You may keep doing the same "cloning" algorithm for non-adjacent vertices even if they have the same degree, and when you terminate you will have a graph $G'$ that has that any non-adjacent vertices have identical neighborhoods (you'd want to start with an indexing of the vertex set do decide which vertex to delete and which to clone so that you are not being circular). Hence, non-adjacency will be a transitive relation, so $G'$ has to look like a complete k-partite graph. Of course, $k\leq 2$, otherwise you have triangles.

Among the complete bipartite graphs, to maximize the number of edges, you should pick the sizes of the parts as close to each other as possible. So you get the desired bound.

You can find many different proofs of Mantel's theorem, and its generalization, Turan's theorem, in Aigner's excellent survey here: http://www.math.caltech.edu/~2014-15/1term/ma121a/Aigner%20-%20Turans%20Graph%20Theorem.pdf

Answer 2

It is the Turan's theorem in the case $r=2$. That Wikipedia page contains a proof. Mantel's theorem (on the same Wikipedia page) is exactly the OP claim.

Answer 3

Theorem. (Mantel, $1907$)

The maximum number of edges in an $n$-vertex triangle free graph is $\left\lfloor\frac{n^2}{4}\right\rfloor$.

Proof. Let $G$ be a triangle-free graph with $n$ vertices and $m$ edges. Let $x$ be a vertex of $G$ of maximum degree, and let $d(x)=k$.

Let $N(x)$ denote the set of vertices adjacent to $x$; thus, $x \notin N(x)$. Since $G$ has no triangle, $u,v \in N(x)$ implies $u \not\leftrightarrow v$. Hence, every edge in $G$ has $x$ as an endpoint or one of the non-neighbours of $x$ as an endpoint. Therefore,

$$ m \le \sum_{v \:\notin\: N(x)} d(v) \le k(n-k) \le \left(\frac{k+(n-k)}{2}\right)^2 = \frac{n^2}{4}. $$

Hence, any graph with at least $\frac{n^2}{4}+1$ edges must contain a triangle.

Indeed, the complete bipartite graph with partite sets of sizes $\left\lfloor\frac{n}{2}\right\rfloor$ and $\left\lceil\frac{n}{2}\right\rceil$ has $\left\lfloor\frac{n}{2}\right\rfloor \cdot \left\lceil\frac{n}{2}\right\rceil = \left\lfloor\frac{n^2}{4}\right\rfloor$ edges and no triangle (because it is bipartite). $\blacksquare$