ステップ 1/4: 部屋Aに最大クリークMを置き、c(A) <= c(B) まで移動させる ざっくり言うとM の全員を部屋 A に置くと c(A)=2m≥c(B) となる。A から B へ一人ずつ移すと、各段階で c(A) は 1 減り c(B) は高々 1 増える。したがって初めて c(A)>c(B) が成り立たなくなったとき、c(B) は k または k+1 であり、M のサイズが偶数の 2m なので k≥m である。
例としての K4 の友人関係グラフ: 4頂点全体が偶数サイズの最大クリークをなす。部屋分けそのものを表す図ではない。詳しい解説c(X) を部屋 X の最大クリークサイズとする。サイズ ∣M∣=2m の最大クリーク M を固定し、A=M、B を残りの全競技者とする。このとき c(A)=2m≥c(B)。c(A)>c(B) の間、A から B へ一人移す。各移動で c(A)=∣A∣ は 1 減り、c(B) は高々 1 増えるので、k=c(A)=∣A∣=∣A∩M∣ で停止したとき k≤c(B)≤k+1 である。さらに k≥m である。そうでなければ ∣A∩M∣≤m−1、∣B∩M∣≥m+1 となり、停止時の c(B)≤c(A)+1 に反して c(B)−c(A)≥(m+1)−(m−1)=2 となる。c(B)=k なら終了であり、以下では c(B)=k+1（k≥m≥∣B∩M∣）と仮定する。