Định lý Turán, trường hợp không tam giác (Định lý Mantel)

Ta quy nạp theo $n$. Với $n \le 2$ khẳng định là hiển nhiên vì $\lfloor n^2/4 \rfloor \ge 0$ và mọi đồ thị trên tối đa 2 đỉnh có tối đa 1 cạnh.

Giả sử khẳng định đúng với mọi đồ thị không tam giác trên ít hơn $n$ đỉnh, và cho $G$ là đồ thị không tam giác trên $n$ đỉnh. Nếu $G$ không có cạnh thì chặn hiển nhiên đúng, nên giả sử $G$ có một cạnh $uv$. Vì $G$ không có tam giác, $u$ và $v$ không có hàng xóm chung, tức $N(u) \cap N(v) = \varnothing$.

Vì $N(u)$ và $N(v)$ là các tập con rời nhau của tập $n$ đỉnh, $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$.

Xóa $u$ và $v$ khỏi $G$ để được đồ thị không tam giác $G'$ trên $n-2$ đỉnh. Mỗi cạnh của $G$ hoặc là cạnh $uv$, hoặc là cạnh từ $u$ hay $v$ đến phần còn lại, hoặc là cạnh của $G'$; đếm cẩn thận ta có $e(G) = e(G') + \deg(u) + \deg(v) - 1$ (số hạng $-1$ điều chỉnh vì cạnh $uv$ được đếm một lần trong $\deg(u)+\deg(v)$ nhưng nó không phải cạnh của $G'$).

Theo giả thiết quy nạp $e(G') \le \lfloor (n-2)^2/4 \rfloor$, nên $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$. Tính trực tiếp cho $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$, và kiểm tra riêng trường hợp $n$ chẵn/lẻ cho thấy $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ đúng. Vậy $e(G) \le \lfloor n^2/4 \rfloor$, hoàn tất quy nạp.

Với trường hợp cực trị, đồ thị lưỡng phân đầy đủ với hai phần kích thước $\lfloor n/2 \rfloor$ và $\lceil n/2 \rceil$ không có tam giác (mọi tam giác cần một cạnh trong cùng một phần, nhưng không có cạnh nào như vậy) và có đúng $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ cạnh, nên chặn này chặt.