第4問

k本の辺をもつ連結グラフGを考える。各辺に

1,2,\ldots,k

を付け、2本以上の辺に接する各頂点で、それらの辺のラベルの最大公約数が1となるようにできることを証明せよ。

ステップ 1/4: 連続ラベルの互いに素性を使う

\gcd(t,t+1)=1

詳しい解説

鍵は任意の連続する正整数の最大公約数が1であること。従って連続ラベルの2辺に接する頂点は、他の接辺に関係なく条件を満たす。