第3問

数学コンテストに参加する競技者の中には友人同士の者がいる。友情は常に相互的である。任意の二人が友人であるような競技者の集合をクリークと呼ぶ。（特に、2人未満の任意の集合もクリークである。）クリークの要素数をそのサイズと呼ぶ。このコンテストでクリークの最大サイズが偶数であるとき、競技者を二つの部屋に配置して、一方の部屋に含まれるクリークの最大サイズと他方の部屋に含まれるクリークの最大サイズが等しくなるようにできることを証明せよ。

ステップ 2/4: B cap M のある x が B の (k+1)-クリークに属さない場合

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

ざっくり言うと

$x$ を $A$ に戻すとクリーク $A \cap M$ はサイズ $k+1$ になり、 $C \subseteq B \setminus \{x\}$ はそのままなので $c(B)$ は $k+1$ のままである。

\\exists\\, x \\in B \\cap M,\\ C \\subseteq B \\text{ clique with } |C| = k+1,\\ x \\notin C \\implies c(A \\cup \\{x\\}) = c(B \\setminus \\{x\\}) = k+1

詳しい解説

$x \in B \cap M$ かつ $x \notin C$ となるサイズ $k+1$ のクリーク $C \subseteq B$ が存在すると仮定する。 $x$ を $B$ から $A$ に戻すと、 $A$ は $M$ の $k+1$ 人からなり $c(A) = k+1$ 。また $C \subseteq B \setminus \{x\}$ はサイズ $k+1$ のまま残り、 $c(B)$ は $k+1$ を超えないので、 $c(B) = k+1 = c(A)$ となり終了する。