方針
(1) 実際の操作列を与える。(2) 十分性はを3ずつ増やす構成で示す。必要性は、各頂点に0または1を置く連立偶奇条件を定め、2種類の操作の前後で解が一対一に対応する不変量を作る。
解答
(1)
3頂点の棒状グラフは、最初の白頂点に操作1を2回続けて施せば得られる。最初の頂点は2回色が反転して白に戻り、新しい2頂点も白である。
4本の葉を持つ星形グラフは、最初の白頂点に操作1を4回施せば得られる。中心は4回反転して白、4個の葉はすべて白である。
最後のグラフは次のように作れる。まず操作1で黒頂点と白頂点を結ぶ。白頂点に操作1を3回施すと、その頂点には白い葉が3本付き、中心と最初の頂点はともに黒になる。この2黒頂点を結ぶ辺に操作2を施すと、両者は白になり、間に白頂点が入る。最後にこの新しい白頂点に操作1を2回施す。すると2つの白い4価頂点が結ばれ、各々に白い葉が3本付いた所要のグラフになる。
(2)
まず十分性を示す。
は出発グラフであり、は(1)で構成した。全白の棒状グラフが可能だとする。その端の白頂点に操作1を施し、次に新しくできた端の白頂点に操作1を施す。端にはが並ぶ。2個の黒頂点を結ぶ辺に操作2を施せば、4頂点とも白の棒となり、頂点数は3増える。従ってならばは可能である。
(2) 必要性
各頂点に数を対応させ、各頂点でを課す。ただしが白なら、黒ならとする。
操作1で頂点に白い新頂点を加えると、新頂点の式はすなわちである。これを色が反転したの式に代入すると、反転で増減したとが打ち消し合い、操作前のの式に戻る。従って操作前後の解は一対一に対応する。
操作2で辺を白い新頂点で2分すると、新頂点の式はすなわちである。これを色が反転したの式に代入すると、それぞれ操作前の式に戻る。従ってこの操作でも解は一対一に対応する。
出発グラフでは式はであり、解は零解だけである。従って可能グラフでは上の連立条件に非零解は存在しない。
ところが、全白の棒状グラフでなら、左からと周期3でを置くと非零解になる。実際、内部では連続する3項の和が偶数で、両端でも隣り合う2項の和が偶数である。これは可能グラフには非零解がないことに反する。
従ってが必要である。十分性と合わせてが必要十分条件である。
別解
解法2(許容する0・1印の個数を不変量にする)
方針
(1) は操作列を簡潔に指定する。(2) は各頂点へ0・1の印を置く規則を定め、その許容配置の個数が2種類の操作で変わらないことを示す。全白の棒では印が周期3で伝わるため、許容配置が1個になる長さを判定する。
解答
(1)
3頂点の棒は、出発頂点に操作1を2回施せば得られる。4本の葉を持つ星は、出発頂点に操作1を4回施せば得られる。
3つ目のグラフは次の順に作る。まず出発頂点 に操作1を施して白い頂点 を加える。 に操作1を3回施すと、 に白い葉が3本付き、 は黒になる。辺 に操作2を施して間に白い頂点 を入れると、 は白へ戻る。最後に に操作1を2回施す。すると が隣接する2つの4価頂点となり、各々に白い葉が3本付く。
(2)
まず構成を示す。 の全白の棒は可能である。全白の 頂点の棒の端に操作1を2回施すと、端に黒、黒、白の3頂点が続く。このうち黒と黒を結ぶ辺に操作2を施せば全部白となり、頂点数が3増える。従ってなら構成できる。
次に必要性を示す。各頂点 に または1の印を置き、次の条件を課す。ただし が白なら 、黒なら0とする。この条件を満たす印の置き方を許容配置と呼ぶ。
操作1で新頂点 を加えると、 の条件から と一意に決まる。これを色が反転した の条件へ戻すと、操作前の条件に一致する。操作2でも新頂点の条件から新しい印が一意に決まり、両端の条件は操作前へ戻る。従って許容配置の個数はどちらの操作でも変わらない。出発グラフでは零配置の1個だけだから、可能グラフの許容配置も1個だけである。
全白の 頂点の棒で、左端の印を とする。左端条件から次の印も 、内部条件から印はと周期3で伝わる。右端条件まで自動的に満たされるのは のときであり、この場合は の2配置がある。これは可能グラフの許容配置が1個であることに反する。
従って必要十分条件はである。
総評
難度10、計算量5。必要性が本問の核心である。一般の行列式やグラフ理論の定理は使わず、0・1の連立偶奇条件を各操作で直接追跡して不変性を証明した。構成側と不可能性側の両方を完結させた。 2解法の数式と最終結論を相互照合し、原典本文との対応、小問の完答、境界条件、図の読み取りを再確認した。





