Good idea, but the OP seems to talk about complete graphs where every pair of vertices is connected.

For bigger N this is way beyond the planar graphs needed for the map coloring problem.

But following the links given leads to Edge coloring, which seems to be fit the problem's description.

and the Example section states:

• A complete graph Kn with n vertices is edge-colorable with n − 1 colors when n is an even number; ...
• However, when n is odd, n colors are needed: ...