第3問

SNS には

2019

人の利用者がおり、そのうちいくつかの組は友達である（友達関係は対称的である）。次のような出来事が繰り返し、一度に一つずつ起こってよい:

A

が

B

と

C

の両方と友達であるが、

B

と

C

は友達でない三人の利用者

A

、

B

、

C

が、友達関係を変更して

B

と

C

が友達になり、

A

は

B

とも友達でなく、

C

とも友達でなくなるようにする。他のすべての友達関係は変わらない。最初、

1010

人の利用者はそれぞれ

1009

人の友達を持ち、

1009

人の利用者はそれぞれ

1010

人の友達を持つ。このような出来事の列の後に各利用者が高々一人の他の利用者と友達になるようにできることを証明せよ。

ステップ 6/6: マッチングで終了する

前のステップ次のステップ

|E_{t+1}|=|E_t|-1,\qquad \text{no legal toggle}\Longleftrightarrow\ \deg(v)\le 1\quad\text{for every }v

詳しい解説

得られた森で、可能なトグルを任意に続ける。各トグルは辺の数を $1$ 減らすので、有限回で必ず終了する。終了時に、もしある頂点 $A$ が二つの隣接頂点 $B,C$ を持てば、非巡回性から $BC$ は存在せず、さらに有効なトグルができる。したがってすべての頂点の次数はたかだか $1$ である。よって最終的な友達グラフは、孤立頂点を合わせたマッチングとなり、要求どおりである。