1998年(平成10年)東京大学後期-数学[3]

例えば，図1のグラフは頂点が 個，辺が 個あり，辺 （，…，）の頂点は と である．， は白頂点であり，，， は黒頂点である．

出発点とするグラフ （図2）は，， であり，ただ1つの頂点は白頂点であるとする．

与えられたグラフ から 新しいグラフ を作る． 種類の操作を以下で定義する．これらの操作では頂点と辺の数がそれぞれ1だけ増加する．

（操作1）この操作は の頂点 を つ選ぶと定まる． は に新しい頂点 を加えたものとする． は に新しい辺 を加えたものとする．
の頂点は と とし， のそれ以外の辺の頂点は での対応する辺の頂点と同じとする． において頂点 の色が白又は黒ならば， における色はそれぞれ黒又は白に変化させる．それ以外の頂点の色は変化させない．また は白頂点にする（図3）．

（操作2）この操作はの辺 を1つ選ぶと定まる．
は に新しい頂点 を加えたものとする． は から を取り去り，新しい辺 ， を加えたものとする． の頂点が と であるとき， の頂点は と であり，
の頂点は と であるとする．
のそれ以外の辺の頂点は での対応する辺の頂点と同じとする． において頂点 の色が白又は黒ならば， における色はそれぞれ黒又は白に変化させる． についても同様に変化させる．それ以外の頂点の色は変化させない．また は白頂点にする（図4）．

出発点のグラフ にこれら 種類の操作を有限回繰り返し施して得られるグラフを可能グラフと呼ぶことにする．次の問いに答えよ．

(1) 図5の つのグラフはすべて可能グラフであることを示せ．ここで，すべての頂点の色は白である．

(2) を自然数とするとき， 個の頂点を持つ図6のような棒状グラフが可能グラフになるために の満たすべき必要十分条件を求めよ．ここで，すべての頂点の色は白である．