Mantelの定理

$4ab=n^2-(a-b)^2$ であり、$a-b=n-2b$ は $n$ と同じ偶奇をもつ。$n$ が偶数なら $(a-b)^2\ge0$ で、等号は $a=b$ のときに限るので、$ab\le n^2/4=\lfloor n^2/4\rfloor$ である。$n$ が奇数なら $a-b$ は奇数で $(a-b)^2\ge1$、等号は $\lvert a-b\rvert=1$ のときに限るので、$ab\le(n^2-1)/4=\lfloor n^2/4\rfloor$ である。$\square$

$G$ の次数が最大の頂点 $v$ を 1 つとり、$\Delta:=d(v)$、$A:=N(v)$、$B:=V(G)\setminus A$ とおく。$\lvert A\rvert=\Delta$、$\lvert B\rvert=n-\Delta$ である。
$G$ は三角形を含まないので、$A=N(v)$ は独立集合であり、$e(A)=0$ である。よって $G$ の辺は、$A$ と $B$ を結ぶ辺か、$B$ の中の辺のどちらかであり、
$$ e(G)=e(A,B)+e(B) $$
である。一方、$B$ の頂点の次数の和 $\sum_{x\in B}d(x)$ では、$A$ と $B$ を結ぶ辺は 1 回、$B$ の中の辺は両端で 2 回数えられるので、$\sum_{x\in B}d(x)=e(A,B)+2e(B)$ である。2 つの式から
$$ e(G)=\sum_{x\in B}d(x)-e(B)\le\sum_{x\in B}d(x)\le\lvert B\rvert\cdot\Delta=\lvert A\rvert\,\lvert B\rvert\le\left\lfloor\frac{n^2}4\right\rfloor $$
を得る。2 つ目の不等号は各頂点の次数が最大次数 $\Delta$ 以下であることにより、最後の不等号は lem-mantel-product による。
等号の場合を調べる。$e(G)=\lfloor n^2/4\rfloor$ なら上の不等号はすべて等号である。1 つ目から $e(B)=0$ なので $B$ は独立集合である。$A$ も独立集合なので、$G$ の辺はすべて $A$ と $B$ を結ぶ。2 つ目から $B$ の各頂点の次数は $\Delta=\lvert A\rvert$ なので、$B$ の各頂点は $A$ のすべての頂点と隣接する。よって $G$ は部 $A,B$ をもつ完全二部グラフ $K_{\lvert A\rvert,\lvert B\rvert}$ である。3 つ目と lem-mantel-product の等号条件から $\bigl\lvert\lvert A\rvert-\lvert B\rvert\bigr\rvert\le1$ なので、$G$ は $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ と同型である。逆に $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ が等号を与えることは上で見た。$\square$

要点：辺 $xy$ の両端 $x,y$ は共通の隣接頂点をもたないので、$x$ または $y$ に接続する辺は $xy$ を含めて高々 $n-1$ 本であり、$\lfloor(n-2)^2/4\rfloor+n-1=\lfloor n^2/4\rfloor$ から帰納法が進む。

辺 $xy$ を含む三角形は、$x$ と $y$ の共通の隣接頂点 $z$ と 1 対 1 に対応する。$N(x)$ と $N(y)$ はどちらも $n$ 個の頂点の部分集合なので
$$ \lvert N(x)\cap N(y)\rvert=\lvert N(x)\rvert+\lvert N(y)\rvert-\lvert N(x)\cup N(y)\rvert\ge d(x)+d(y)-n $$
である。三角形は 3 本の辺を含むので、すべての辺について足すと各三角形がちょうど 3 回数えられ、
$$ 3T(G)=\sum_{xy\in E(G)}\lvert N(x)\cap N(y)\rvert\ge\sum_{xy\in E(G)}\bigl(d(x)+d(y)\bigr)-nm $$
となる。右辺の和では頂点 $x$ の項 $d(x)$ が $x$ に接続する辺の本数、すなわち $d(x)$ 回現れるので、和は $\sum_xd(x)^2$ に等しい。握手補題（次数(グラフ) の記事）により $\sum_xd(x)=2m$ なので、Cauchy–Schwarzの不等式により $\sum_xd(x)^2\ge(2m)^2/n$ である。よって
$$ 3T(G)\ge\frac{4m^2}n-nm=\frac{4m}{n}\left(m-\frac{n^2}4\right) $$
である。$\square$

prf-mantel-main と同じく、最大次数の頂点 $v$ をとり $A:=N(v)$、$B:=V(G)\setminus A$ とおく。そこで示した等式と不等式により
$$ \left\lfloor\frac{n^2}4\right\rfloor-k\le e(G)=\sum_{x\in B}d(x)-e(B)\le\lvert A\rvert\,\lvert B\rvert-e(B)\le\left\lfloor\frac{n^2}4\right\rfloor-e(B) $$
なので、$e(B)\le k$ である。$B$ の中の $e(B)$ 本の辺を取り除くと、$A$ も $B$ も独立集合になるので、残りのグラフは部 $A,B$ をもつ二部グラフである。$\square$

二部グラフでないグラフは奇数の長さの閉路をもつ（二部グラフ の定理「閉路の長さによる特徴付け」）ので $C$ は存在する。三角形を含まないので長さは $3$ でなく、$2k+1\ge5$ である。$C$ の頂点を巡る順に $c_0,c_1,\dots,c_{2k}$ とする。

1. $C$ の上で隣り合わない 2 頂点 $c_i,c_j$ が隣接したとする。$C$ はこの 2 頂点で長さ $a,b$（$a+b=2k+1$、$a,b\ge2$）の 2 本の道に分かれ、それぞれに辺 $c_ic_j$ を加えると長さ $a+1$ と $b+1$ の閉路ができる。$a+b$ は奇数なので $a,b$ の一方、たとえば $a$ が偶数で、長さ $a+1$ の閉路は奇数の長さをもつ。$b\ge2$ より $a+1\le2k<2k+1$ となり、$C$ の最短性に反する。
2. $C$ の上にない頂点 $u$ が $C$ の 2 頂点 $c,c'$ と隣接したとする。$C$ は $c,c'$ で長さ $a,b$（$a+b=2k+1$、$a,b\ge1$）の 2 本の道に分かれ、それぞれに $u$ を通る 2 辺を加えると長さ $a+2$、$b+2$ の閉路ができる。$a$ が奇数なら長さ $a+2$ の閉路は奇数の長さなので、最短性から $a+2\ge2k+1$、すなわち $b=2k+1-a\le2$ である。$b$ は偶数なので $b=2$ である。$b$ が奇数の場合も同様に $a=2$ である。つまり、$u$ の $C$ の上の隣接頂点のどの 2 つも、$C$ に沿って距離ちょうど 2 の位置にある。$u$ が $C$ の 3 頂点と隣接したとすると、番号を付け替えて $c_0$ とし、ほかの 2 つは $c_0$ から距離 2 の位置 $c_2$ と $c_{2k-1}$ である。$c_2$ と $c_{2k-1}$ の $C$ に沿った距離は $\min(2k-3,4)$ であり、これが $2$ になるのは $2k=5$ のときだけで、$k$ が整数であることに反する。$\square$

lem-mantel-odd-cycle の $C$（長さ $2k+1$、$k\ge2$）をとり、$C$ の外の頂点の個数を $r:=n-2k-1\ge0$ とする。$G$ の辺を、$C$ の頂点どうしを結ぶもの、$C$ と外を結ぶもの、外どうしを結ぶものに分ける。補題の 1 により前者は $2k+1$ 本、補題の 2 により 2 番目は $2r$ 本以下である。外の頂点で誘導される部分グラフは三角形を含まない $r$ 頂点のグラフなので、thm-mantel-main により辺は $r^2/4$ 本以下である。よって
$$ e(G)\le\frac{r^2}4+2r+2k+1 $$
である。$n-1=r+2k$ を使うと
$$ \left(\frac{(n-1)^2}4+1\right)-\left(\frac{r^2}4+2r+2k+1\right)=rk+k^2-2r-2k=(r+k)(k-2)\ge0 $$
なので $e(G)\le(n-1)^2/4+1$ であり、$e(G)$ は整数だから主張の上界が従う。
達成されること：長さ 5 の閉路の頂点 $1,2,3,4,5$ を、それぞれ大きさ $1,1,1,x,y$（$x=\lfloor(n-3)/2\rfloor$、$y=\lceil(n-3)/2\rceil$）の独立集合 $P_1,\dots,P_5$ に置き換え、$P_i$ と $P_{i+1}$（添字は 5 を法とする）の頂点をすべて結んだグラフを $G_n$ とする。隣接する 2 頂点は隣り合う異なる $P_i$ に属するので、三角形があれば閉路の上で互いに隣り合う 3 つの $P_i$ があることになり、長さ 5 の閉路にそのような 3 頂点はないので、$G_n$ は三角形を含まない。$P_1,\dots,P_5$ から 1 頂点ずつ選ぶと長さ 5 の閉路があるので二部グラフでない。辺は $1+1+x+xy+y=xy+(n-3)+2$ 本で、lem-mantel-product により $xy=\lfloor(n-3)^2/4\rfloor$ なので、$\lfloor(n-3)^2/4\rfloor+(n-3)+1=\lfloor(n-1)^2/4\rfloor$ と合わせて $e(G_n)=\lfloor(n-1)^2/4\rfloor+1$ である。$\square$

$G$ が二部グラフでないとして、lem-mantel-odd-cycle の $C$（長さ $2k+1\ge5$）をとる。$C$ の頂点の次数の和 $\sum_{c\in C}d(c)$ は、各頂点 $u$ について「$u$ に隣接する $C$ の頂点の個数」を足したものに等しい。補題により、この個数は $C$ の頂点では $2$、$C$ の外の頂点では高々 $2$ なので
$$ \sum_{c\in C}d(c)\le2n $$
である。一方、仮定から左辺は $(2k+1)\cdot\frac{2n}5$ より大きく、$2k+1\ge5$ なので $2n$ 以上である。これは矛盾である。
後半：$t\ge1$ とし、長さ 5 の閉路の各頂点を大きさ $t$ の独立集合に置き換えた（prf-mantel-nonbipartite で $x=y=1$ の代わりにすべての大きさを $t$ にした）グラフを考える。頂点は $n=5t$ 個で、三角形を含まず、二部グラフでない（長さ 5 の閉路を含む）。各頂点は隣り合う 2 つの集合の $2t=2n/5$ 個の頂点と隣接する。$\square$