ひらめきなどない

東大98後期3
略解
直線グラフだけ考えればいいことは点から出ている辺の数が減らないことから明らか。

直線のグラフ G に対して、次の整数の非順序対を考え、特性数と呼ぶ。

A(G) = 端から黒丸を二つずつ組にしていき、組の中の距離の和
1.G の黒丸の数が偶数の場合
{A(G), A(G の両端に黒丸を付け加えたもの)}
2.G の黒丸の数が奇数の場合
{A(G の右端に黒丸を付け加えたもの), A(G の左端に黒丸を付け加えたもの)}

たとえば、
白丸が n 個つづいている場合、
{0, n+1} が特性数である。

特に白丸が 1つならば、{0,2}

ところで、与えられた操作は、すべて特性数の差を3で割った余りを保存する。
よって、特性数が{0,3n}とあらわされる白丸が3n-1つながっているグラフは
白丸が1つのグラフから上述の操作では生成できない。

なぜこれが簡単なのだろうか。
軽く実験をすればどのようなものが可能グラフかは容易に判断できる。
つまり、長さを 3 で割った余りで分類できるようだということだ。
そうなると、すべての直線のグラフから移り変わる関係を保存するような簡単な関手が存在するだろう。
黒丸を消滅させる操作は、隣同士をまとめて消すか端のものをひとつ消すかだ。
そうすると、上の特性数の概念にたどりつく。
あとはどの操作でもこれが保存していることを確認すれば終わり。