\(N > 6\) の場合について、公式解説とは別の max = 3 の構築を示します。

頂点を \(L = \{1, \ldots, \lfloor n / 2 \rfloor\}, R = \{\lfloor n / 2 \rfloor + 1, \ldots, n\}\) の二つの集合に分割します。

以下のように辺の値を定めます。

• \(L\) 同士、\(R\) 同士なら \(1\)
• \(L, R\) 間の辺は、偶奇が異なれば \(2\)、等しければ \(3\)

この構築が条件を満たすことを確認します。

単調増加なパスが存在したとします。 一度 \(L, R\) 間の辺を使用すると、\(L, R\) 内の辺を使うことができなくなることから、ありうるパスは \(L \rightarrow R \rightarrow L \cdots\) と移動することになります。(ただし、\(n\) が奇数のときは最初の \(R\) 内を移動する可能性がある。)

一方、パリティの条件より、\(N > 5\) のときこのような移動は不可能であることがわかります。