第3問

SNS には

2019

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

A

が

B

と

C

の両方と友達であるが、

B

と

C

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

A

、

B

、

C

が、友達関係を変更して

B

と

C

が友達になり、

A

は

B

とも友達でなく、

C

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

1010

人の利用者はそれぞれ

1009

人の友達を持ち、

1009

人の利用者はそれぞれ

1010

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

ステップ 5/6: 木の内部で閉路を作らずにトグルする

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

T\text{ a tree},\quad AB,AC\in E(T),\ BC\notin E(T)\Longrightarrow\ T'=(T\setminus\{AB,AC\})\cup\{BC\}\text{ is a forest}

詳しい解説

ここで、上で得た全域木を $T$ とする。頂点 $A$ が二つの隣接頂点 $B,C$ を持つとき、 $B$ から $C$ への唯一の道は $B-A-C$ なので、 $B$ と $C$ は隣接せず、トグルは有効である。木から $AB$ と $AC$ を除くと三つの成分に分かれ、 $BC$ を加えると $B$ と $C$ を含む二成分が結ばれる。したがって結果は（辺が一つ少ない）森であり、閉路は生じない。同じ議論は、その後のすべての森にも適用できる。