大学への数学  「９９年１２月の宿題」

［答］
　背理法を使って証明しよう。
　適当な定数kは任意のnに対して、Ｇ(n)はk−彩色可能とする。

　すると、十分大きなnに対して、

　Ｇ(n)の部分集合Ｕ(１)＝｛(i , i＋１)｜i＝1,2,3,･･･｝とする。
このＵ(１)のうち同色の頂点が一番多いの選び、それを
Ｖ(１)＝｛(ａi , ａi＋１)｜i＝1,2,3,･･･｝とする。

つぎに、Ｇ(n)の部分集合Ｕ(２)＝｛(ａ2i−１ , ａ2i )｜i＝1,2,3,･･･｝とする。
Ｕ(２)は、Ｖ(１)と辺で結ばれているので、Ｖ(１)以外の色である。
このうち同色の頂点が一番多いの選び、それを
Ｖ(２)＝｛(ｂi , ｃi)｜i＝1,2,3,･･･｝とする。作り方よりｂi ＜ ｃi ＜ ｂi＋１

また、Ｇ(n)の部分集合Ｕ(３)＝｛(ｂ2i−１ , ｂ2i )｜i＝1,2,3,･･･｝とする。
Ｕ(３)は、Ｖ(１)とＶ(２)に辺で結ばれているので、Ｖ(１)とＶ(２)以外の色で
ある。このうち同色の頂点が一番多いの選び、それを
Ｖ(３)＝｛(ｄi , ｅi)｜i＝1,2,3,･･･｝とする。作り方よりｄi ＜ ｅi ＜ ｄi＋１

また、Ｇ(n)の部分集合Ｕ(４)＝｛(ｄ2i−１ , ｄ2i )｜i＝1,2,3,･･･｝とする。
Ｕ(４)は、Ｖ(１)とＶ(２)とＶ(３)に辺で結ばれているので、それらの３色以外
の色である。このうち同色の頂点が一番多いの選び、それを
Ｖ(４)＝｛(ｆi , ｇi)｜i＝1,2,3,･･･｝とする。作り方よりｆi ＜ ｇi ＜ ｆi＋１

　という風に繰り返すと、十分大きなnに対して、Ｕ( k＋１)が存在することに
なるが、これは、各Ｖ(i)（i＝1,2,3,･･･,k）と辺で結ばれているので、もう色
の種類がない。
　よって、Ｇ(n)はk−彩色可能ではない。

　よって、題意を満たす。