東京大学 1998年度
後期・理系数学 後期 第3問

解答

(1)

3頂点の棒状グラフは、最初の白頂点に操作1を2回続けて施せば得られる。最初の頂点は2回色が反転して白に戻り、新しい2頂点も白である。

4本の葉を持つ星形グラフは、最初の白頂点に操作1を4回施せば得られる。中心は4回反転して白、4個の葉はすべて白である。

最後のグラフは次のように作れる。まず操作1で黒頂点と白頂点を結ぶ。白頂点に操作1を3回施すと、その頂点には白い葉が3本付き、中心と最初の頂点はともに黒になる。この2黒頂点を結ぶ辺に操作2を施すと、両者は白になり、間に白頂点が入る。最後にこの新しい白頂点に操作1を2回施す。すると2つの白い4価頂点が結ばれ、各々に白い葉が3本付いた所要のグラフになる。

(2)

まず十分性を示す。$n=1$は出発グラフであり、$n=3$は(1)で構成した。全白の棒状グラフ$C_k$が可能だとする。その端の白頂点に操作1を施し、次に新しくできた端の白頂点に操作1を施す。端には

が並ぶ。2個の黒頂点を結ぶ辺に操作2を施せば、4頂点とも白の棒

となり、頂点数は3増える。従って$n\equiv 0,1(\mathrm{mod}3)$ならば$C_n$は可能である。

(2) 必要性

各頂点$v$に数$x_v\in \{0,1\}$を対応させ、各頂点で

を課す。ただし$v$が白なら${\epsilon }_v=1$、黒なら${\epsilon }_v=0$とする。

操作1で頂点$v$に白い新頂点$z$を加えると、新頂点の式は

すなわち$x_z=x_v$である。これを色が反転した$v$の式に代入すると、反転で増減した$x_v$と$x_z$が打ち消し合い、操作前の$v$の式に戻る。従って操作前後の解は一対一に対応する。

操作2で辺$uv$を白い新頂点$z$で2分すると、新頂点の式は

すなわち$x_z=x_u+x_v$である。これを色が反転した$u,v$の式に代入すると、それぞれ操作前の式に戻る。従ってこの操作でも解は一対一に対応する。

出発グラフでは式は$x_1=0$であり、解は零解だけである。従って可能グラフでは上の連立条件に非零解は存在しない。

ところが、全白の棒状グラフで$n=3m+2$なら、左から

と周期3で$x_v$を置くと非零解になる。実際、内部では連続する3項の和が偶数で、両端でも隣り合う2項の和が偶数である。これは可能グラフには非零解がないことに反する。

従って$n\not\equiv 2(\mathrm{mod}3)$が必要である。十分性と合わせて

が必要十分条件である。