第3問

SNS には

2019

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

A

が

B

と

C

の両方と友達であるが、

B

と

C

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

A

、

B

、

C

が、友達関係を変更して

B

と

C

が友達になり、

A

は

B

とも友達でなく、

C

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

1010

人の利用者はそれぞれ

1009

人の友達を持ち、

1009

人の利用者はそれぞれ

1010

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

ステップ 2/6: 次数と辺の数を追跡する

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

\deg'(A)=\deg(A)-2,\qquad \deg'(B)=\deg(B),\qquad \deg'(C)=\deg(C),\qquad |E'|=|E|-1

詳しい解説

$A,B,C$ におけるトグルでは、頂点 $A$ は辺 $AB$ と $AC$ の両方を失うので、その次数はちょうど $2$ だけ減り、偶奇は変わらない。頂点 $B$ は辺 $AB$ を失うが辺 $BC$ を得て、頂点 $C$ は $AC$ を失うが $BC$ を得るので、それらの次数はまったく変わらない。他のすべての頂点は影響を受けない。したがってトグルは常にグラフからちょうど一つの辺を取り除き、どの頂点の次数の偶奇も決して変えない。