必要条件を満たす \(K\) に対する構築方法について述べます．

グラフの辺集合を，次のように完全マッチングに分割できます．

• マッチング \(t\)：\((x, (x+t)\bmod N)\) を結ぶ辺全体．

さらにマッチング \(2t,2t+1\) を合わせるとサイクルになります．

\(N\) が偶数のとき

辺集合を，\(m = N/2\) 個のサイクルに分割します． \(k\) 番目のサイクルには区間 \([2Nk, 2N(k+1))\) の値を割り当てることを前提とします．すると，作るべきウォークはサイクル内のウォークを結合したものとして書けます．

これの長さが \(K\) になるように調整します．各サイクルでの長さを \((2N,2N,\ldots,2N, x, 2, 2, 2, \ldots)\) のように割り当てます．

\(2N\) の部分は，サイクル上で長さ \(2N\) のウォーク \(0\to 0\) がとれるようにします．

\(2\) の部分は，サイクル上の重みが \(0,N,1,N+1,2,N+2,\ldots\) のような感じに並ぶように調整すると，どこからスタートしても最大長さ \(2\) のウォークがとれるようにできます．

あとは \(x\) の部分です．要するにサイクルの辺に重みを付けて，重みが増大するパスの最大長が \(x\) かつ始点 \(0\) のときになるようにすればよいのです．これは簡単にできます．

\(N\) が奇数のとき

同じように完全マッチング \(2t,2t+1\) を合わせることで，辺集合を，\(((N-1)/2)\) 個のサイクルと完全マッチング \(1\) つに分割できます．

最後にひとつ余っている完全マッチング部分で長さ \(1\) のウォークが追加することを除き，偶数のときとほぼ同じ構築が可能です．