If \(N\) is odd, there is a solution based on neighbouring diagonals in adjacency matrix. E.g. for \(N = 5\):

5 5 3 3 1 1
4 5 5 3 3 4
4 4 5 5 3 3
2 4 4 5 5 2
2 2 4 4 5 5

In graph terms:

1. for \(1 \leq i, j \leq N\) the color of the edge \(v_i u_j\) depends only on \({\lfloor (j - i) / 2 \rfloor}\),
2. the edge \(v_i u_{N + 1}\) extends the unique path terminating at \(v_i\).

For even \(N\) this construction does not quite work, since after part 1 there are either two or zero paths terminating at each \(v_i\). However, it is possible to repeat part 1 of the odd construction for \(1 \leq i, j \leq N - 1\), and extend the paths to \(v_N, u_N, u_{N + 1}\) with minor adjustments. Details are given below.

If \(N = 2\), there is no solution. Otherwise, for even \(N\) we produce a solution as follows :

• For \(1 \leq i, j \leq N - 1\) we color \(v_i u_j\) in one of the colors \(2, \ldots, N\) based on \(\lfloor (j - i) / 2 \rfloor\). E.g. for \(N = 6\):

6 6 4 4 2 . .
5 6 6 4 4 . .
5 5 6 6 4 . .
3 5 5 6 6 . .
3 3 5 5 6 . .
. . . . . . .

• Extend each path \(2, \ldots, N\) to the bottom row (in a unique way), and to one of the rightmost free columns, so that each path uses edges \(v_{2i - 1, j}, v_{2i, j}\) for some \(1 \leq i \leq N / 2\), and \(j \in \{N, N + 1\}\). Additionally, create the path \(1\) out of remaining two edges, making sure it’s in the same column as path \(2\):

6 6 4 4 2 5 2
5 6 6 4 4 5 2
5 5 6 6 4 4 3
3 5 5 6 6 4 3
3 3 5 5 6 6 1
6 3 4 5 2 6 1

• The only problem is that path \(N\) is now in fact a cycle. We solve this by shuffling around paths \(1\), \(2\), and \(N\):

6 6 4 4 2 5 2
5 6 6 4 4 5 1
5 5 6 6 4 4 3
3 5 5 6 6 4 3
3 3 5 5 6 6 1
2 3 4 5 2 6 6