グラフ とは有限個の頂点の集合 とそれらの間を結ぶ辺の集合 からなる図形を指す．各辺 は丁度2つの頂点 () を持つ．頂点以外の辺の交わりは考えない．さらに，頂点には白か黒の色がついていると仮定する．
例えば，図1のグラフは頂点が 個，辺が 個あり，辺 () の頂点は と である． は白頂点であり， は黒頂点である．
出発点とするグラフ (図2) は， であり，ただ1つの頂点は白頂点であるとする．
与えられたグラフ から新しいグラフ を作る2種類の操作を以下で定義する．これらの操作では頂点と辺の数がそれぞれ1だけ増加する．
(操作1) この操作は の頂点 を1つ選ぶと定まる． は に新しい頂点 を加えたものとする． は に新しい辺 を加えたものとする． の頂点は と とし， のそれ以外の辺の頂点は での対応する辺の頂点と同じとする． において頂点 の色が白又は黒ならば， における色はそれぞれ黒又は白に変化させる．また， は白頂点とする (図3)．
(操作2) この操作は の辺 を1つ選ぶと定まる． は に新しい頂点 を加えたものとする． は から を取り去り，新しい辺 を加えたものとする． の頂点が と であるとき， の頂点は と であり， の頂点は と であるとする． のそれ以外の辺の頂点は での対応する辺の頂点と同じとする． において頂点 の色が白又は黒ならば， における色はそれぞれ黒又は白に変化させる． についても同様に変化させる．それ以外の頂点の色は変化させない．また， は白頂点とする (図4)．
出発点のグラフ にこれら2種類の操作を有限回繰り返して得られるグラフを可能グラフと呼ぶことにする．次の問いに答えよ．
(1) 図5の3つのグラフはすべて可能グラフであることを示せ．ここで，すべての頂点の色は白である．
(2) を自然数とするとき， 個の頂点を持つ図6のような棒状グラフが可能グラフになるための を満たす必要十分条件を求めよ．ここで，すべての頂点の色は白である．
図 1
