Turánの定理、三角形を含まない場合(Mantelの定理)

$n$ について帰納法を用いる。$n \le 2$ では $\lfloor n^2/4 \rfloor \ge 0$ であり、高々2頂点のグラフは高々1辺しか持たないため主張は自明である。

$n$ 未満の頂点数を持つすべての三角形を含まないグラフで主張が成り立つと仮定し、$G$ を $n$ 頂点上の三角形を含まないグラフとする。$G$ に辺がなければ限界は自明に成り立つので、$G$ が辺 $uv$ を持つと仮定する。$G$ は三角形を含まないため、$u$ と $v$ は共通の隣接点を持たない、すなわち $N(u) \cap N(v) = \varnothing$ である。

$N(u)$ と $N(v)$ は $n$ 頂点集合の互いに素な部分集合であるから、$\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$ が成り立つ。

$G$ から $u$ と $v$ を取り除いて $n-2$ 頂点上の三角形を含まないグラフ $G'$ を得る。$G$ の各辺は辺 $uv$ であるか、$u$ または $v$ から残りへの辺であるか、$G'$ の辺であるかのいずれかであり、注意深く数えると $e(G) = e(G') + \deg(u) + \deg(v) - 1$ が成り立つ(この $-1$ は辺 $uv$ が $\deg(u)+\deg(v)$ の中で一度数えられるが $G'$ の辺ではないことを補正する)。

帰納法の仮定より $e(G') \le \lfloor (n-2)^2/4 \rfloor$ なので、$e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$ である。直接計算すると $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$ となり、$n$ の偶奇を個別に確認すると $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ が正確に成り立つ。したがって $e(G) \le \lfloor n^2/4 \rfloor$ となり、帰納法が完了する。

極値の場合、大きさ $\lfloor n/2 \rfloor$ と $\lceil n/2 \rceil$ の部分を持つ完全二部グラフは三角形を含まず(三角形には同じ部分内の辺が必要だがそのような辺は存在しない)、ちょうど $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ 本の辺を持つため、この限界は最良である。