\(N\) 個の頂点からなる無向グラフを考える. 交換できる 2 頂点間に辺を引くことで交換可能を表すことにすると, グラフが連結になれば全頂点が交換可能となり, 目標を達成できる.

まず, \(i \leq N-A\) の頂点と \(i+A\) の頂点を辺でつなぐ. こうすると, \(A\) 個の木からなる森ができる.

次に \(i \leq N-B\) の頂点と \(i+B\) の頂点を辺でつなぐことを考える.

\(A, B\) が互いに素でない場合は達成できない. \(g = \gcd(A, B)\) とすると, \(i \mod g = 0\) を満たす \(i\) 番目の木は \(j \mod g = 1\) を満たす \(j\) 番目の木には接続できないからである.

また, \(A\) 個の木をつなぐには最低でも \(A-1\) 本の辺が必要となる. よって, \(N-B \geq A-1\) でなければならない. 逆にこれが成り立てば, \(A, B\) は互いに素であることから, \(A-1\) 本の辺が結ぶ 2 頂点を \(A\) で割ったときの余りは異なるので, これで連結にできる.