一方で，補題 59と握手補題より，
∑
u∈V(G)
( dG(u)
)2
≥ 1 n
( ∑
u∈V(G)
dG(u) )2
= 4|E(G)|2 n が成り立つため，変形して所望の不等式を得る． □
演習 33 定理 58のそれぞれの証明において，n が偶数のときに等号を満たす場合を考え，
そのようなグラフを決定せよ．
演習 34 G を n 頂点 m 辺のグラフとする．このとき，Gは少なくとも 4m
3n (
m− n2 4
)
個の三角形を持つことを示せ．
ヒント：Mantelによる定理 58 の証明を利用せよ．特に，G の各辺uv に対し，uv を含 む三角形は dG(u) +dG(v)−n 個以上存在する．これを用いて，次の集合の要素数を2通 りに評価せよ．
S = {
(uv, T) : uv ∈E(G), T は辺 uv を含むG の三角形} .
定理 58 のさらに別の証明 G を n 頂点の三角形を持たないグラフで辺数が最大のもの とする．まず，次の主張を示す．
主張 59.1 G は次の性質を満たす 3頂点u, v, w を持たない：uv, uw ̸∈E(G) だが vw∈ E(G) である．
u
v w
図 36: 3頂点 u, v, w.
u v
w
u v
w v′
図 37: 主張59.1 の証明の，場合 1におけるグラフの変形．
証明． そのような 3 頂点u, v, w が存在したと仮定する．(図 36 参照．) このとき，次 の 2つのそれぞれの場合で矛盾を導く．
場合 1: dG(u)< dG(v) またはdG(u)< dG(w) である．
対称性よりdG(u)< dG(v)としてよい．このとき，グラフ Gの次の変形を考える．(図 37 参照)
頂点u を取り除き，N(v′) =N(v) となるように新しい頂点 v′ を加える．
ここで，新しいグラフを G′ と書く．ただし vv′ ̸∈E(G′) であることに注意する．このと き，G′ が三角形 T を持つとすると，G は三角形を持たないため，T は頂点 v′ を含む．
しかしvv′ ̸∈E(G′)であるため，T は v は含まず，したがってv′ の代わりに v を用いる ことで Gの三角形が見つかり矛盾する．
したがって，G′ は三角形を持たないが，
|E(G′)| = |E(G)| −dG(u) +dG′(v′) = |E(G)| −dG(u) +dG(v) > |E(G)| であり，G を三角形を持たない辺数最大のグラフとしたことに矛盾する．
場合 2: dG(u)≥dG(v) かつdG(u)≥dG(w) である．
このとき，グラフ G の次の変形を考える．
頂点 v, wを取り除き，N(u′) = N(u′′) = N(u)となるように新しい頂点u′, u′′
を加える．
ここで，新しいグラフを G′′ と書く．場合 1と同じ理由で G′′ は三角形を持たず，
|E(G′′)| = |E(G)| −(
dG(v) +dG(w)−1)
+ 2dG(u) > |E(G)| であり，同じく矛盾を得て，主張 59.1 の証明が終了した． □
では，主張 59.1 を用いて定理58を証明する．ここで，2 頂点u, v に対し，
uv ̸∈E(G)である，かつそのときに限り u∼v となる，
ようなV(G) の 2項関係∼ を定義する．主張 59.1 より ∼ は推移律を満たし同値関係と なる．この同値類は G で独立頂点集合となり，また異なる同値類に属す 2頂点は辺で結 ばれている．したがって，G は三角形を持たないことから同値類は高々 2 つであり，G は辺のないグラフ，または完全 2部グラフ Kn1,n2 と同型になる．(ただしn1+n2 =n．) 辺数の最大性より前者が起こらないことが自明にわかり，また，次の式から証明が終了 する．
|E(Kn1,n2)| = n1n2 ≤ ⌊n 2
⌋⌈n 2
⌉
. □
演習 35 上の証明を利用し次を示せ: G を n 頂点で K4 を部分グラフとして持たないグ ラフとする．このとき，次が成り立つ．
|E(G)| ≤ n2 3 .
一般にこれをさらに拡張した次の結果が同様の手法によって証明できる．
定理 60 (Tur´an, 1941) G を n 頂点で Kk+1 を部分グラフとして持たないグラフとす る．このとき，次が成り立つ．
|E(G)| ≤ ( 1− 1
k )n2
2
演習 ∗ 定理60 を示せ．また，等号が成り立つ例を特徴付けよ．