第3問
SNS には 人の利用者がおり、そのうちいくつかの組は友達である（友達関係は対称的である）。次のような出来事が繰り返し、一度に一つずつ起こってよい: が と の両方と友達であるが、 と は友達でない三人の利用者 、、 が、友達関係を変更して と が友達になり、 は とも友達でなく、 とも友達でなくなるようにする。他のすべての友達関係は変わらない。最初、 人の利用者はそれぞれ 人の友達を持ち、 人の利用者はそれぞれ 人の友達を持つ。このような出来事の列の後に各利用者が高々一人の他の利用者と友達になるようにできることを証明せよ。
詳しい解説
各利用者の次数は か なので、隣接しない任意の二利用者の隣接数の和は少なくとも となり、鳩の巣原理により共通の隣人が存在する。したがって初期グラフ は連結である。 頂点の完全グラフには次数 が必要なので、完全グラフではない。ステップ2により、各トグルで次数が変わる頂点はただ一つで、しかも変化量は だけなので、すべての頂点の次数の偶奇は永遠に固定される。奇数次数 で始まった頂点は、閉路がその頂点に要求する偶数次数 に決して到達できないので、 は閉路には決してならない。ステップ3により、連結でまだ木になっていない限り をトグルし続けてよく、そのようなトグルはそれぞれ辺の数を厳密に減らすので、この過程は必ず停止する:それは、グラフが 頂点すべてを含む全域木になったときにちょうど停止する。