Can you show a solution for 5 nodes? Or for 3 nodes? I fear it's nor possible to write a program to solve an unsolvable problem.

I understand "adjacent" as "having a common vertex". 

#! /usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use Data::Dumper;
use Storable qw{ dclone };

my @LABELS = 'a' .. 'z';

sub add_edge {
    my ($edges) = @_;

    for my $v1 (sort keys %$edges) {
        for my $v2 (sort keys %$edges) {
            next if $v2 <= $v1
                 || exists $edges->{$v1}{$v2};

            my %labels = map { $_ => undef } @LABELS[0 .. keys(%$edges
+) - 2];
            delete @labels{ values %{ $edges->{$v1} },
                            values %{ $edges->{$v2} } };
            next unless keys %labels;

            for my $l (sort keys %labels) {
                my $e = dclone($edges);
                $e->{$v1}{$v2} = $e->{$v2}{$v1} = $l;

                unless (grep keys %{ $e->{$_} } != keys(%$e) - 1, keys
+ %$e) {
                    print Dumper $e;
                    exit
                }
                add_edge($e);
            }
        }
    }
}

my @vertices = (1 .. shift);
my %edges = (1 => {map {2 + $_ => $LABELS[$_]} 0 .. $#vertices - 1});
$edges{2 + $_} = {1 => $LABELS[$_]} for 0 .. $#vertices - 1;

add_edge(\%edges);

[download]

Update: Fixed a bug in the code. It's now still running searching for the solution for 5 nodes.

Update: The code now shows solutions for sizes 4, 6, and 8; and also shows there's no solution for sizes 3 and 5. Checking all the possibilities for larger sizes seems to be very slow.

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

In reply to Re: Graph labeling problem by choroba
in thread Graph labeling problem by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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! —
  • 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:
    & &amp;
    < &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.