定理 61の上界はほぼ最善であることも知られている．すなわち，次の定理が成り立つ．
この証明において用いられている手法も，前章に現れた有限幾何である．(実際に，ここで の nの値で p=t−1とおくと演習 30で現れる n の値となるが，これは偶然ではない．) 定理 62 任意の素数 p と n=p2+p+ 1 に対し，四角形を持たないようなn 頂点のある グラフ Gで次が成り立つ．
|E(G)| = n−1 4
(1 +√
4n−3) .
証明． 素数 pを法とする有限体 Zp 上の 3次元ベクトル空間 X を考える．すなわち，
X ={
v = (v1, v2, v3) :vi ∈Zp, i= 1,2,3}
で，演算として各座標の Zp での和を考える．(以下注意しないが，和は Zp で考える．) ここで，X の一つのベクトル v に対し，[v]で v が生成する1次元部分空間を表す．(た だしv ̸= 0 = (0,0,0) とする．) すなわち，
[v] ={
u:u=kv, 0≤k≤p−1} である．特に，[v]=p となる．
ここで，グラフ Gp を次のように定義する．
V(Gp) = {
[v] :v ∈X− {0}} , かつ E(Gp) = {
[v][w] : [v]̸= [w], ⟨v,w⟩=v1w1+v2w2+v3w3 = 0} . ここで “⟨v,w⟩ = 0” である，という性質は [v] と [w] の代表元の取り方に依存しない ため，この定義は well-defined である．(すなわち，kv ∈[v] に対し，⟨v,w⟩= 0 ならば
⟨kv,w⟩= 0 である．)
演習 37 p= 3 のとき，上のグラフ G3 を図示せよ．
このとき，各 1次元部分空間 [v] は 0 でないベクトルをちょうどp−1 個含み，ベク トル空間 X は 0 でないベクトルをちょうどp3−1個含む．また，X の二つのベクトル v と w に対し，[v]∩[w] ={0}であるか [v] = [w]であるため，
|V(Gp)| = p3−1
p−1 =p2+p+ 1 = n である．
ここでGp の2頂点[v]と[w]に対し，Gp において共通近傍[u]が存在したと仮定する．
つまり，[u][v],[u][w]∈E(Gp) である．このとき，Gp の辺の定義より，u = (u1, u2, u3) は次の線形方程式系の解 x= (x1, x2, x3) となる:
v1x1+v2x2+v3x3 = 0, w1x1+w2x2 +w3x3 = 0.
ただし，v = (v1, v2, v3)かつ w = (w1, w2, w3)としている．ここで [v]と [w] はGp の異 なる頂点であり，そのため v と w は 1次独立である．したがって，上の線型方程式系の
解空間の次元は 1であり[u] がその1次元部分空間と一致する．これより，[v] と[w]の Gp における共通近傍 [u] は一つしかなく，Gp に四角形は存在しない．
最後に，Gp の辺数を握手補題によって与える．Gp の各頂点[v]に対し，線形方程式系 v1x1+v2x2+v3x3 = 0
を考えると，その解空間 Xv の次元は 2 となる．特に，Xv は 0 でないベクトルをちょ うど p2−1個含み，X の各 1次元部分空間は0 でないベクトルをちょうど p−1個含む ため，Xv はちょうど
p2−1
p−1 =p+ 1 個の1次元部分空間を含む．
頂点 [v] の Gp での近傍はこの 1次元部分空間たちであり，したがって，次数は高々 p+ 1 である．これより，2|E(Gp)| ≤(p+ 1)n であり，n=p2+p+ 1 から得られる等式 p= −1+√24n−3 を使い，
|E(Gp)| ≤ (p+ 1)n
2 = n
4
(1 +√
4n−3) は得られる．
これをもっと詳しく見よう．上の Xv は，ちょうど p+ 1 個の 1次元部分空間を含む．
これらが [v] のGp での近傍のように見えるが，このp+ 1個のうちの一つは自分自身[v]
かもしれず，その分を除く必要がある．したがって，Gp の各頂点 [v] に対し，次のこと が成り立つ．
dGp([v]) =
{p+ 1 (v1)2+ (v2)2+ (v3)2 ̸= 0 のとき，
p (v1)2+ (v2)2+ (v3)2 = 0 のとき． (7) そこで，次数が p の頂点の数を決めるため，方程式 (x1)2 + (x2)2 + (x3)2 = 0 の解 x = (x1, x2, x3) の個数を調べる必要がある．実際に次が成り立つ．
主張 62.1 方程式 (x1)2+ (x2)2+ (x3)2 = 0 の解は，ちょうど p+ 1 個の[v]からなる．
主張 62.1 の証明は後に回し，まずは，これが正しいとして定理 62の証明を完了させる．
主張 62.1 と式(7) より，Gp で次数が pであるような [v]はちょうど p+ 1 個である．
ここで Gp の頂点数が p2+p+ 1 であることから，次数 p+ 1 の頂点はちょうどp2 個存 在し，
2|E(Gp)| = p(p+ 1) + (p+ 1)p2 = p(p+ 1)2 である．さらに n=p2+p+ 1 を使って計算を進め，
|E(Gp)| = p(p+ 1)2
2 = p2+p 4
(1 + (2p+ 1))
= n−1 4
(1 +√
4n−3) となり，証明が終了する．したがって，後は主張 62.1 を示せばよい．
主張 62.1 の証明．
X の 1次元部分空間を適当な順で[v(1)],[v(2)], . . . ,[v(n)] と書く．これに対し，次のよ うなn×n の行列 A を考える：
A の i行 j列の成分は，⟨v(i),v(j)⟩= 0 のとき 1で，そうでないとき 0．
このとき，v(i) が方程式 (x1)2 + (x2)2 + (x3)2 = 0 の解であるための必要十分条件は，
⟨v(i),v(i)⟩= 0 であることなので，A の定義より，主張62.1 を示すためには A の対角成 分にある 1の個数がわかれば良い．そのために，Aの trace(対角成分の和)を計算する．
ここで用いる性質は下のものである：
traceA = (A の固有値の和).
さらに A の固有値を求めるために，A2 を考える．特に，
• A の i行は，線形方程式系
v1(i)x1+v2(i)x2+v(i)3 x3 = 0
の解 x= (x1, x2, x3) たちで作られる 1次元部分空間に対応する箇所に 1 が与えら れている．(ただし，v(i)= (v1(i), v2(i), v3(i))とおいている．)すでに見たように，その ような1次元部分空間は p+ 1 個存在する．したがって，A2 の i 行i 列成分(対角 成分)は p+ 1 となる．
また，各行の和が p+ 1 なので，p+ 1 が A の固有値である．なぜならば，1 を全 成分が 1のベクトルとすると，A1= (p+ 1)1 であるため，p+ 1 が A の固有値で 1 が対応する固有ベクトルとわかるからである．
• A の第i 行と第 j 行を考える．これは，上と同様に考えると，線形方程式系 v1(i)x1+v2(i)x2+v3(i)x3 = 0
v1(j)x1+v2(j)x2+v(j)3 x3 = 0
の解 x= (x1, x2, x3) に対応する箇所で同時に1 が与えられている．そのような解 は，やはりすでに見たように，ちょうど一つの1次元部分空間をなしている．これ が A2 の i行 j列の成分に対応しており，その値は 1 である．
以上より，A2 は次のような形をしている．
A2 =
p+ 1 1 · · · 1 1 p+ 1 · · · 1 ... ... . .. ... 1 1 · · · p+ 1
=pI+J.
ただし，J はすべての成分が 1のn×nの正方行列で，I は単位行列である．ここで，J は 固有値 n (重複度1)と 0 (重複度 n−1)を持つ．したがって，A2 は固有値はn+p(重複 度1)とp(重複度n−1)を持つ．Aは実対称行列で対角化可能であるので，A の固有値は
±√
n+p(重複度1)と±√p(合わせて重複度n−1)である．上で述べたようにp+ 1がA の固有値であるが，これが一つ目のものに対応している．(√
n+p=√
p2 + 2p+ 1 =p+ 1 に注意．)これより，A の固有値において√p の重複度をs，−√p の重複度を t とそれぞ れおくと，
trace A = (A の固有値の和) = (p+ 1) +s√
p−t√ p
であるが，A の対角成分の和は整数でありp は素数であるため，s=t が成り立ち，Aの 対角成分の和はちょうど p+ 1 である．これで主張 62.1 の証明が終了した． □
演習 ∗ p= 3 のとき，上の証明中の行列 A と A2 を与えよ．