\(N=2,3\) の場合は条件を達成することは不可能です。\(N = 5\) の場合は sample にあるように \(\max\) が \(4\) のケースを構築出来ます。また、全探索によって \(N = 5\) の場合 \(\max\) が \(3\) 以下のケースを構築できないことも確認できます。上記以外の場合は \(\max\) が \(3\) のケースを構築出来ること、\(\max\) が \(2\) 以下のケースを構築出来ないことを示します。

全ての辺に \(1\) か \(2\) がついている完全グラフでは通る辺についた番号が単調増加である全ての頂点を通るパスが取れることを帰納法で示します。\(N\) 頂点のグラフ \(G\) に対して、頂点 \(N\) を取り除いたグラフ \(G'\) で条件を満たすパス \((p_1,p_2,\dots,p_{N-1})\) を取ります。もしこのパスの辺についた番号が全て等しいなら頂点 \(N\) を先頭か末尾に追加出来ます。そうでないとき、\(p_i,p_{i+1}\) 間の辺には \(1\) がついていて、\(p_{i+1},p_{i+2}\) 間の辺には \(2\) がついているような \(i\) を取ることが出来ます。このとき、\(p_{i+1}\) と頂点 \(N\) 間の辺についた数字が \(1\) の場合は \((p_1,\dots,p_i,p_{i+1},N,p_{i+2},\dots,p_{N-1})\)、\(2\) の場合は \((p_1,\dots,p_i,N,p_{i+1},p_{i+2},\dots,p_{N-1})\) のように頂点 \(N\) を挿入出来るため、示されました。

さて、\(\max\) が \(3\) になるケースを構築しましょう。頂点を \(4\) 個の集合 \(X_0,X_1,X_2,X_3\) に分けます。ただし、\(|X_0| \ge |X_1| \ge |X_2| \ge |X_3| \ge |X_0| - 1\) となるようにします。そして、\(X_i,X_j(i \le j)\) 間の辺は以下のように張ります。

• \((i,j) = (0,1),(2,3)\) の場合 \(1\) をつける。
• \((i,j) = (0,3),(1,2)\) の場合 \(2\) をつける。
• \((i,j) = (0,0),(1,1),(2,2),(3,3),(0,2),(1,3)\) の場合 \(3\) をつける。

もしこのグラフ上で辺の番号が単調増加なパスが取れたとしましょう。始点が \(X_0\) に含まれるとします。すると、あり得るパターンは以下の \(2\) 通りです。

• \(X_0\) と \(X_1\) 間を複数回往復する。その後、\(X_0\) と \(X_3\) 間を複数回往復する。更にその後、\(X_0,X_2\) の頂点を適当に移動する。

• \(X_0\) と \(X_1\) 間を複数回往復する。\(X_0\) から \(X_1\) に移動する。その後、\(X_1\) と \(X_2\) 間を複数回往復する。更にその後、\(X_1,X_3\) の頂点を適当に移動する。

上のパターンのときは、\(|X_0| \ge |X_1| + |X_3| + 1\) となっている必要があるため不適です。下のパターンのときは、\(|X_1| \ge |X_0| + |X_2|\) となっている必要があるためこの場合も不適です。

始点が \(X_1,X_2,X_3\) に含まれる場合もそれぞれ以下の不等式が成り立つ必要があり不適であることが分かります。

• \(|X_1| \ge |X_0| + |X_2| + 1\)
• \(|X_0| \ge |X_1| + |X_3|\)
• \(|X_2| \ge |X_3| + |X_1| + 1\)
• \(|X_3| \ge |X_2| + |X_0|\)
• \(|X_3| \ge |X_2| + |X_0| + 1\)
• \(|X_2| \ge |X_3| + |X_1|\)

よって、上記の構築が条件を満たすことが証明出来ました。

補足として、\(|X_0| \ge |X_1| \ge |X_2| \ge |X_3| \ge |X_0| - 1\) が成り立たない場合は条件を満たさない可能性があることに注意してください。例えば \((|X_0|,|X_1|,|X_2|,|X_3|) = (2,1,2,1)\) のようにした場合は \(|X_0| \ge |X_1| + |X_3|\) が成り立ってしまうため不適です。