実は，定理 55は次の定理の系としても得られる．ここで，完全グラフKn に対し，そ の部分グラフたち H1, H2, . . . , Hm が「Kn のどの辺も，ちょうど一つの Hi に含まれる」
という性質を満たすとき，Kn は H1, H2, . . . , Hm へと分割されているという．
定理 56 完全グラフ Kn が部分完全グラフ H1, H2, . . . , Hm へと分割されているならば，
m= 1 またはm ≥n である．
演習 28 平面上の一直線上にないn 点の集合 S に対し，S を頂点集合とし，平面上で同 一直線上にある 2点を辺で結んだグラフをG とする．このグラフ G を用いて，定理55 が定理 56の系であることを説明せよ．
定理 56 の証明． 完全グラフ Kn が部分完全グラフ H1, H2, . . . , Hm へと分割されてい るとし，m̸= 1 かつm < n であると仮定する．このとき，放電法を用いて矛盾を導く．
初期電荷として，各頂点に +1の電荷を与える．このときの電荷の合計は nである．各 頂点 x は，x を含まない ような Hi たちに等分に電荷を渡す．すなわち，x を含まない ようなHi たちの個数をrx とおくと，x はそのようなHi のそれぞれへ，ちょうど 1
rx の 電荷を渡す．
各頂点 x と x を含まない Hk の組を考えると，次の不等式が成り立つ．
m−rx ≥ |Hk|.
なぜならば，Hk に含まれる各頂点y に対し，Kn の辺xy たちはそれぞれ異なる Hi に 含まれており，左辺 m−rx は「x を含むHi たちの個数」を表しているからである．こ れより，
rx≤m− |Hk| が得られる．
ここで，各部分完全グラフ Hk が受け取る電荷の総量を考えよう．Hk は x̸∈V(Hk)と なる各頂点 x より 1
rx の電荷を受け取るため，合計で少なくとも
∑
x̸∈V(Hk)
1
rx ≥ ∑
x̸∈V(Hk)
1 m− |Hk|
の電荷を受け取る．ここで，x̸∈V(Hk)である頂点 xは全部で n− |Hk| 個存在するため，
∑
x̸∈V(Hk)
1
rx ≥ ∑
x̸∈V(Hk)
1
m− |Hk| = n− |Hk| m− |Hk| > n
m
である．なお，最後の不等号は n > m かつ |Hk| ≥1 から得た．よって，放電後の電荷 の合計を計算すると，
n= (電荷の合計)> m· n m =n となり矛盾である． □
演習 29 定理 56の結論 m≥n が最善であることを示す例を与えよ．
定理 56 の結論 m ≥ n は「すべての Hi の大きさが等しい」という条件を要求したと しても，いくつかの n ではやはり最善であることが知られている．例えば，n = 7 の 7 個の完全グラフへの分割として，次のような例が存在する．
V(K7) = {0,1,2,3,4,5,6} に対し，H1, . . . , H7 を次のように定める．
V(H1) ={0,1,6}, V(H2) = {0,2,5}, V(H3) ={0,3,4}, V(H4) = {1,2,4}, V(H5) ={1,3,5}, V(H6) = {2,3,6}, V(H7) ={4,5,6}.
これはファノ平面と呼ばれる平面から作られる．実は，定理 56が定理 55の拡張であっ たように，この問題は通常のものとは異なる幾何として述べられている．(そのような幾 何学は，特に有限幾何と呼ばれている．) 実際に，上のK7 の分割の例は，図 34 にある ファノ平面 から作られている．
0 1
2 3
4 5
6
図 34: ファノ平面．
演習 30 Kn を「すべての Hi の大きさが等しい」ような部分完全グラフ H1, H2, . . . , Hn へと分割できたとする．このとき，n は，ある整数t に対し n =t2−t+ 1 と書けるが，
これを示せ．
そのような n で 7の次に小さいものは 13 である (t = 4 のとき)が，実際に，n = 13 のときにはそのような分割は存在する．
演習 ∗ K13 を n 個の部分完全グラフで同じ大きさのものへと分割せよ．
定理 57 完全グラフ Kn が部分完全2部グラフ H1, H2, . . . , Hm へと分割されているなら ば，m≥n−1 である．
証明． 完全グラフKn が部分完全2部グラフH1, H2, . . . , Hm へと分割されているとし，
m < n−1であると仮定する．各Hi は完全2部グラフであり，それぞれの部集合をLi, Ri
とおく．
Kn の各頂点 v に変数 Xv を与える．H1, H2, . . . , Hm が Kn の分割なので，
∑
u,v∈V(Kn),u̸=v
XuXv =
∑m i=1
( ∑
s∈Li
Xs·∑
t∈Ri
Xt )
(6) が成り立っている．ここで，次の線型方程式系を考える．
∑
v∈V(Kn)
Xv = 0,
∑
s∈Li
Xs = 0 (i= 1, . . . , m).
これは n 個の変数に対しm+ 1 < n 本の線形方程式からなっており，したがって，自明 でない解 Xv =αv (v ∈V(Kn)) を持つ．このとき，式(6) の右辺の ∑
の各i において，
∑
s∈Liαs= 0 であることから，
∑
u,v∈V(Kn),u̸=v
αuαv = 0 を得る．よって，∑
v∈V(Kn)αv = 0 であることより, 0 = ( ∑
v∈V(Kn)
αv )2
= ∑
v∈V(Kn)
α2u+ ∑
u,v∈V(Kn),u̸=v
αuαv = ∑
v∈V(Kn)
α2u となる．しかしながら，αv (v ∈V(Kn))が自明でない解であることから，∑
v∈V(Kn)α2u >0 となり，矛盾がおこる． □
次の例が定理 57の最善の例となっている．Kn に対し，n = 1 では辺が存在せず，分 割の意味がないため n≥2とする．ここで，1頂点v を固定し，v に接続するすべての辺 からなる完全2部グラフ K1,n−1 を Hn−1 とおく．Kn からその頂点 v を取り除いた完全 グラフ Kn−1 を考え，以下帰納的に，完全2部グラフ K1,n−2, . . . K1,1 をとると，これは n−1個の完全2部グラフよりなる Kn の分割である．(図 35に n= 5 の場合を示す．)
K5 H4 H3 H2 H1
図 35: H1, H2, H3, H4 によるK5 の分割．各 Hi は K1,i と同型である．
演習 31 図 35 の例(1≤i≤n−1で Hi が K1,i の場合) において，各 Hi で Li が 1点 側としたときに定理 57の証明内の方法でできる線形方程式系を示し，その解が自明なも のしか存在しないことを確認せよ．また，逆に各 iで Ri が 1 点側としたときも考えよ．