『入試数学伝説の良問100』という本に、入試史上最難問として
東大の1998年後期の問3(2)が載っていて、
解答を見ると行列を使った長ったらしい証明が書かれてあったんだけど、
次のように考えると簡単に証明できる。

まずちょっとした工夫として、操作1と操作2を統一的に扱うため、
白い頂点が1個のグラフから出発するかわりに、
白い頂点が3個直線状に連なったグラフから出発し、
操作1は使わず操作2のみを用いてグラフを変化させていく。
両端の頂点を無視すれば、もとの問題の方法で作られるグラフと
この方法で作られるグラフが対応することが分かる。
次に、ある状態のグラフについて、
黒い頂点が端から何番目にあるかを並べた数列
b1,b2,…,bk (b1>b2>…>bk; kは黒い頂点の個数で必ず偶数になる)
を考えると、
b1-b2+b3-…-bk+n (nはグラフの頂点の個数)
という式の値が常に3の倍数になることが分かる。
このことは、最初の工夫により、簡単な場合分けで示すことができる。
よって、両端を除いた頂点が全て白ならば、
その個数を3で割った余りは0または1となる。
逆に、3で割った余りが0または1となるものが作れることは
簡単に示せる。

これが史上最難問ってのはちょっと大袈裟なのではと思った。