分解に直接取り組む代わりに、2n+1 個の点を 0 から 2n まで円周上にラベル付けし、その巡回距離によって K2n+1 の各辺を彩色する:辺 ij は、両端点が一方向に k 歩離れているとき色 k を得る。もし木 T の1つのコピーがたまたま n 色すべてをちょうど1回ずつ使う(「虹色」コピー)なら、その1つのコピーを円周上で 2n+1 回回転させるだけで、K2n+1 のすべての辺を使い尽くす 2n+1 個の互いに素なコピーが得られる——回転は色を保ち、各色クラスは1回の回転ごとにちょうど1回使い切られるからである。
every ND-coloured K2n+1 has a rainbow copy of every n-edge tree
詳しい解説
ロサはリンゲル予想への優美な標識アプローチを導入し、コツィヒはそれを虹色部分グラフの言葉で再定式化した(モンゴメリー・ポクロフスキー・スダコフ2021年、第1節)。K2n+1 の頂点集合 {0,…,2n} を固定し、近距離(ND)彩色を定義する:colour edge ij by k∈[n] if i≡j+k or j≡i+k(mod2n+1)。コツィヒは、ND彩色された K2n+1 が a rainbow copy of T has all its n edges in distinct colours を含むなら、その1つの虹色コピーの 2n+1 回の巡回シフトは互いに辺素であり、合わせて K2n+1 を分解することに気づいた。なぜならシフトは辺を同じ色の別の辺へと送るだけだからである。コツィヒはさらに、虹色コピーが常に存在すると予想した。モンゴメリー、ポクロフスキー、スダコフの定理2.1は、大きな n に対してまさにこれを証明し、コツィヒの観察により直ちにリンゲルの定理1.2が導かれる。
このステップの用語
虹色部分グラフ
辺彩色されたグラフの部分グラフで、すべての辺が異なる色を持つもの。
ND彩色(近距離彩色)
頂点 {0,…,2n} 上の K2n+1 の辺彩色で、両端点が巡回的に k だけ離れている辺に色 k を割り当てるもの(k∈[n])。