Complete GraphのHamilton cycle(path)への分割

Modern Graph Theory/Bela Bollobasからあまりウェブ上にないトピックをば.
・r-正則グラフとは
無向グラフで全ての頂点からr本の枝が出ているものを言います.
特に
頂点数をnとして(n-1)-正則グラフのことを完全グラフと言います.
・ハミルトン閉路/パス(Hamilton cycle)とは
全ての頂点を重複なく通過する閉路/パスのことを言います.
あるグラフ上にハミルトン閉路が存在するかという問題は
ハミルトン閉路問題と呼ばれ,それなりに難しいクラスの問題(NP-完全)であることが分かっています.
しかし完全グラフの場合そのグラフにハミルトン閉路/パスが存在するかどうかは次のように分かります.
(互いに辺素とは2つのグラフが同じ辺を使用していないことを言います)

定理:
任意のn に対して
nが3 以上の奇数ならばKn(n個の頂点
を持つ完全グラフ) は
(n-1)/2個のHamilton cycle に分割できる.n が2 以
上の偶数ならばKn はn/2 個のHamilton path に分割できる.


証明:
n が偶数(2k) の時を考える.各ノードに0,1,2,3,...,k,...,-3,-2,-1 と番号付
ける.この時s,s+1,s-1,s+2,s-2,s+3,s-3,...,s+k とパスを取ればこれはハミルトンパス
である.このパスを始点 を0 からk-1 まで変化させてk-1 個のパス を取る.

図1:n=6の時のハミルトンパスの取り方

(ノードの番号付けはなんだって構いません.)
各頂点 において
端点のノードの番号の差の絶対値の同じ枝は2つあり
それぞれ異なるパス に属するから,
このパスが辺素であることがわかりn が偶数の時には示せた.
n が奇数の時には一つの頂点を固定し
その頂点を除去したグラフはK(n-1)になる
このK(n-1)に対して同じようにHamiltonpath を取り,

図2:n=7の時のハミルトンサイクルの取り方

その始点
と終点に対して固定した頂点から枝 を張れば,
辺素なハミルトン閉路 になっている.

つまりnが偶数の時にギザギザにパスを取りハミルトンパスでかつ
互いに辺素であることを示し,
nが奇数の時は一本間引いて偶数の場合に帰着させれば良いという感じです.
ギザギザのパスはなかなか気づきません.