MathLabs

第3問

SNS には 20192019 人の利用者がおり、そのうちいくつかの組は友達である（友達関係は対称的である）。次のような出来事が繰り返し、一度に一つずつ起こってよい: AA が BB と CC の両方と友達であるが、BB と CC は友達でない三人の利用者 AA、BB、CC が、友達関係を変更して BB と CC が友達になり、AA は BB とも友達でなく、CC とも友達でなくなるようにする。他のすべての友達関係は変わらない。最初、10101010 人の利用者はそれぞれ 10091009 人の友達を持ち、10091009 人の利用者はそれぞれ 10101010 人の友達を持つ。このような出来事の列の後に各利用者が高々一人の他の利用者と友達になるようにできることを証明せよ。
ステップ 3/6: 完全グラフ・閉路・木のいずれでもない連結グラフには安全なトグルが存在する
前のステップ次のステップ
G connected, G≠K∣V∣, G≠C∣V∣, G not a tree ⟹ ∃ A,B,C: G′ connectedG\ \text{connected},\ G\neq K_{|V|},\ G\neq C_{|V|},\ G\ \text{not a tree}\ \Longrightarrow\ \exists\, A,B,C:\ G'\ \text{connected}
詳しい解説

GG が連結だが完全グラフ・閉路・木のいずれでもないとする。このとき GG は閉路を含むが、それ自身がその閉路ではない。最短の閉路 C0C_0 を取る。GG に三角形がなければ、C0C_0 上のある頂点 aa に隣接し C0C_0 の外にある頂点 bb を選び（GG は連結で C0C_0 より大きいので存在する）、cc を C0C_0 上で aa に隣接する頂点とする。C0C_0 の最短性から bb と cc は隣接しないので、a,b,ca,b,c でのトグルは有効であり、aa は閉路上のもう一方の隣接頂点を保持し、bb は新しい辺で cc に再接続されるため、グラフは連結なまま保たれる。逆に GG に三角形があれば、極大な完全部分グラフ KK（頂点全体の真部分集合）と、a∈Ka\in K から b∉Kb\notin K への辺を取る。極大性より bb と隣接しない頂点 c∈Kc\in K が存在し、a,b,ca,b,c でのトグルは有効であり、aa は KK の残りと結び付いたままで bb は cc を通じて再接続されるため、グラフは連結なまま保たれる。