第4問

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

1,2,\ldots,k

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

ステップ 3/4: 最初の端点を処理する

\gcd\{\text{labels at }A\}=1\quad\text{or}\quad\deg(A)=1

詳しい解説

最初の路では最初の辺にラベル1を付ける。従って始点Aが2本以上の辺に接すれば最大公約数は1。1本だけなら条件は不要。終点Bは葉であるか、既に内部または処理済みで安全である。