第4問

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

1,2,\ldots,k

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

ステップ 2/4: 各極大未ラベル路に連続ラベルを付ける

e_1,e_2,\ldots,e_s\quad\mapsto\quad q,q+1,\ldots,q+s-1

詳しい解説

頂点Aから始め、未ラベル辺を辿って未ラベル辺のない端点Bまで進む。通った辺に未使用の連続するラベルを付ける。路の内部頂点は連続ラベル2つに接するので安全である。