Proof of Mantel's Theorem

1.1k Views Asked by At

There is already a proof verification question on the site about Mantel's theorem, but the other proof looks very different to mine, uses Cauchy-Schwarz, etc.

First of all, the theorem:

Theorem (Mantel's Theorem). A graph $G$ is maximally triangle-free with respect to edges only if $$m = \left\lfloor\frac{n^2}{4}\right\rfloor.$$

Now my proof is by induction on the number of vertices. The idea is to take advantage of the fact that the desired graph is $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, which we actually know from Turán's theorem.

Proof. Suppose $G$ is an $n$-vertex graph on $m$ edges that contains no triangles. Then any two adjacent vertices $u$ and $v$ cannot share a common neighbour, so $N(u) \cap N(v) = \varnothing$. Thus \begin{align*} \deg(u) + \deg(v) = |N(u)| + |N(v)| &= |N(u) \cup N(v)| - |N(u) \cap N(v)|\\ &\leqslant |V(G)| - |\varnothing| = n. \end{align*} Now remove two adjacent vertices $u$ and $v$ from $G$ to get $G'$. By induction, this has $\lfloor (n-2)^2/4\rfloor$ edges. Thus \begin{align*} m &= \left\lfloor\frac{(n-2)^2}{4}\right\rfloor + \deg(u) + \deg(v) - 1 \qquad\text{(since $\deg(u) + \deg(v)$ counts $\{u,v\}$ twice)}\\ &\leqslant \frac{(n-2)^2}{4} + n - 1 = \frac{n^2}{4}. \end{align*} It suffices to show that a triangle-free graph on $n$ vertices and $\lfloor n^2/4\rfloor$ edges always exists, since it must have maximal edges by the inequality $m \leqslant n^2/4$ we have just obtained. Indeed, the complete bipartite graph $K_{\lfloor n/2\rfloor, \lceil n/2\rceil}$ has no odd cycles and in particular no triangles, is on $\lfloor n/2\rfloor + \lceil n/2\rceil = n$ vertices and has $$\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil = \begin{cases} \displaystyle\left(\frac{n}{2}\right)\left(\frac{n}{2}\right) = \frac{n^2}{4} = \left\lfloor \frac{n^2}{4} \right\rfloor & \text{if $n$ is even}\\[15pt] \displaystyle\left(\frac{n-1}{2}\right)\left(\frac{n+1}{2}\right) = \frac{n^2 - 1}{4} = \left\lfloor \frac{n^2}{4} \right\rfloor & \text{if $n$ is odd} \end{cases} $$ edges, as required. $\square$

I'd appreciate any feedback about this proof.