And here a generalized minimal and polynomial solution for all N.

( update IOW this can't possibly be improved anymore. It calculated a solution for 1000 nodes in less than a second )

I just realized that a solution for even N can be constructed from previous odd N-1 (you just connect the uncolored "gap" node with the new node, see output).

This means get_edges could be further simplified...

use v5.12;
use warnings;
use Data::Dump qw/pp dd/;


# https://perlmonks.org/?node_id=11141490

calc($_) for 5..10;

exit;


sub rotate(\@) {
    my $r = shift @{$_[0]};
    push @{$_[0]},$r
}

sub get_edges {
    my @verts  = @{+shift};
    my $center = shift;

    my $left  = $#verts/2;
    my @res = map [ $verts[$_-1], $verts[-$_] ], 1..$left;
    push @res,[$center,$verts[$left]]
      if defined $center;
    return \@res;
}

sub get_matrix{
    my (@colored) = @_;
    my @inc_matrix;
    while ( my ($color,$color_set) = each @colored ) {
        for my $edge (@$color_set) {
            my ($v0,$v1) = @$edge;
            $inc_matrix[ $v0 ][ $v1 ] = $color;
            $inc_matrix[ $v1 ][ $v0 ] = $color;
        }
    }
    return \@inc_matrix;
}

sub calc {
    my ( $n ) = @_ ;
    my @nodes = 0 .. $n-1;

    my $center = $n%2
      ? undef
        : pop @nodes;

    my @colored;
    for (@nodes) {
        push @colored, get_edges(\@nodes, $center);
        rotate(@nodes);
    }

    say "\n";
    print "="x10;
    say " N=$n";
    say "=== Colors: ", scalar @colored;
    say "=== Edges: ";
    say pp \@colored;
    say "=== Color Matrix:";
    say pp get_matrix(@colored);
}
[download]

OUTPUT:

========== N=5
=== Colors: 5
=== Edges: 
[
  [[0, 4], [1, 3]],
  [[1, 0], [2, 4]],
  [[2, 1], [3, 0]],
  [[3, 2], [4, 1]],
  [[4, 3], [0, 2]],
]
=== Color Matrix:
[
  [undef, 1, 4, 2, 0],
  [1, undef, 2, 0, 3],
  [4, 2, undef, 3, 1],
  [2, 0, 3, undef, 4],
  [0, 3, 1, 4],
]


========== N=6
=== Colors: 5
=== Edges: 
[
  [[0, 4], [1, 3], [5, 2]],
  [[1, 0], [2, 4], [5, 3]],
  [[2, 1], [3, 0], [5, 4]],
  [[3, 2], [4, 1], [5, 0]],
  [[4, 3], [0, 2], [5, 1]],
]
=== Color Matrix:
[
  [undef, 1, 4, 2, 0, 3],
  [1, undef, 2, 0, 3, 4],
  [4, 2, undef, 3, 1, 0],
  [2, 0, 3, undef, 4, 1],
  [0, 3, 1, 4, undef, 2],
  [3, 4, 0, 1, 2],
]


========== N=7
=== Colors: 7
=== Edges: 
[
  [[0, 6], [1, 5], [2, 4]],
  [[1, 0], [2, 6], [3, 5]],
  [[2, 1], [3, 0], [4, 6]],
  [[3, 2], [4, 1], [5, 0]],
  [[4, 3], [5, 2], [6, 1]],
  [[5, 4], [6, 3], [0, 2]],
  [[6, 5], [0, 4], [1, 3]],
]
=== Color Matrix:
[
  [undef, 1, 5, 2, 6, 3, 0],
  [1, undef, 2, 6, 3, 0, 4],
  [5, 2, undef, 3, 0, 4, 1],
  [2, 6, 3, undef, 4, 1, 5],
  [6, 3, 0, 4, undef, 5, 2],
  [3, 0, 4, 1, 5, undef, 6],
  [0, 4, 1, 5, 2, 6],
]


========== N=8
=== Colors: 7
=== Edges: 
[
  [[0, 6], [1, 5], [2, 4], [7, 3]],
  [[1, 0], [2, 6], [3, 5], [7, 4]],
  [[2, 1], [3, 0], [4, 6], [7, 5]],
  [[3, 2], [4, 1], [5, 0], [7, 6]],
  [[4, 3], [5, 2], [6, 1], [7, 0]],
  [[5, 4], [6, 3], [0, 2], [7, 1]],
  [[6, 5], [0, 4], [1, 3], [7, 2]],
]
=== Color Matrix:
[
  [undef, 1, 5, 2, 6, 3, 0, 4],
  [1, undef, 2, 6, 3, 0, 4, 5],
  [5, 2, undef, 3, 0, 4, 1, 6],
  [2, 6, 3, undef, 4, 1, 5, 0],
  [6, 3, 0, 4, undef, 5, 2, 1],
  [3, 0, 4, 1, 5, undef, 6, 2],
  [0, 4, 1, 5, 2, 6, undef, 3],
  [4, 5, 6, 0 .. 3],
]


========== N=9
=== Colors: 9
=== Edges: 
[
  [[0, 8], [1, 7], [2, 6], [3, 5]],
  [[1, 0], [2, 8], [3, 7], [4, 6]],
  [[2, 1], [3, 0], [4, 8], [5, 7]],
  [[3, 2], [4, 1], [5, 0], [6, 8]],
  [[4, 3], [5, 2], [6, 1], [7, 0]],
  [[5, 4], [6, 3], [7, 2], [8, 1]],
  [[6, 5], [7, 4], [8, 3], [0, 2]],
  [[7, 6], [8, 5], [0, 4], [1, 3]],
  [[8, 7], [0, 6], [1, 5], [2, 4]],
]
=== Color Matrix:
[
  [undef, 1, 6, 2, 7, 3, 8, 4, 0],
  [1, undef, 2, 7, 3, 8, 4, 0, 5],
  [6, 2, undef, 3, 8, 4, 0, 5, 1],
  [2, 7, 3, undef, 4, 0, 5, 1, 6],
  [7, 3, 8, 4, undef, 5, 1, 6, 2],
  [3, 8, 4, 0, 5, undef, 6, 2, 7],
  [8, 4, 0, 5, 1, 6, undef, 7, 3],
  [4, 0, 5, 1, 6, 2, 7, undef, 8],
  [0, 5, 1, 6, 2, 7, 3, 8],
]


========== N=10
=== Colors: 9
=== Edges: 
[
  [[0, 8], [1, 7], [2, 6], [3, 5], [9, 4]],
  [[1, 0], [2, 8], [3, 7], [4, 6], [9, 5]],
  [[2, 1], [3, 0], [4, 8], [5, 7], [9, 6]],
  [[3, 2], [4, 1], [5, 0], [6, 8], [9, 7]],
  [[4, 3], [5, 2], [6, 1], [7, 0], [9, 8]],
  [[5, 4], [6, 3], [7, 2], [8, 1], [9, 0]],
  [[6, 5], [7, 4], [8, 3], [0, 2], [9, 1]],
  [[7, 6], [8, 5], [0, 4], [1, 3], [9, 2]],
  [[8, 7], [0, 6], [1, 5], [2, 4], [9, 3]],
]
=== Color Matrix:
[
  [undef, 1, 6, 2, 7, 3, 8, 4, 0, 5],
  [1, undef, 2, 7, 3, 8, 4, 0, 5, 6],
  [6, 2, undef, 3, 8, 4, 0, 5, 1, 7],
  [2, 7, 3, undef, 4, 0, 5, 1, 6, 8],
  [7, 3, 8, 4, undef, 5, 1, 6, 2, 0],
  [3, 8, 4, 0, 5, undef, 6, 2, 7, 1],
  [8, 4, 0, 5, 1, 6, undef, 7, 3, 2],
  [4, 0, 5, 1, 6, 2, 7, undef, 8, 3],
  [0, 5, 1, 6, 2, 7, 3, 8, undef, 4],
  [5 .. 8, 0 .. 4],
]
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.