第3問
SNS には 人の利用者がおり、そのうちいくつかの組は友達である（友達関係は対称的である）。次のような出来事が繰り返し、一度に一つずつ起こってよい: が と の両方と友達であるが、 と は友達でない三人の利用者 、、 が、友達関係を変更して と が友達になり、 は とも友達でなく、 とも友達でなくなるようにする。他のすべての友達関係は変わらない。最初、 人の利用者はそれぞれ 人の友達を持ち、 人の利用者はそれぞれ 人の友達を持つ。このような出来事の列の後に各利用者が高々一人の他の利用者と友達になるようにできることを証明せよ。