EGMO 2017
問題 4

任意の単調増加な正整数列 $t_1,t_2,\dots,t_n$ について，$t_n+1$ 個の頂点からなる単純グラフであって，各頂点の次数の集合が $\{t_1,t_2,\dots,t_n\}$ と一致するものが存在することを示せばよい．$t_n$ に関する帰納法で示す．

$t_n=1$ のときは明らかである．$t_n\leq m$ のとき成り立つと仮定して，$t_n=m+1$ のときを示そう．$n=1$ のときは明らかなので $n\geq 2$ とする．$t_n+1$ 個の頂点を $t_1,t_n-t_{n-1},t_{n-1}-t_{1}+1$ 個に分け，それぞれグループ $A,B,C$ とする．このとき，仮定より以下のように辺を配置することができる．

• $A$ の頂点は他の頂点全てと辺で繋がれている．
• $B$ の頂点は $A$ の頂点以外とは辺で繋がれていない．
• $C$ の頂点は，$C$ 内の次数の集合が $\{t_2-t_1,t_3-t_1,\dots,t_{n-1}-t_1\}$ に一致する．

このとき頂点全ての次数の集合は $\{t_1,t_2,\dots,t_n\}$ に一致する．