solution.txt

0 -> 1
1 -> 2
2 -> 0
0 -> 3
3 -> 2
2 -> 7
7 -> 1
1 -> 5
5 -> 0
0 -> 4
4 -> 3
3 -> 8
8 -> 2
2 -> 0
0 -> 1
1 -> 6
6 -> 5
5 -> 4
4 -> 9
9 -> 3
3 -> 0
0 -> 4
4 -> 10
10 -> 5
5 -> 4
4 -> 3
3 -> 2
2 -> 1
1 -> 5
5 -> 10
10 -> 9
9 -> 8
8 -> 7
7 -> 6
6 -> 10
10 -> 11
11 -> 6
6 -> 1
1 -> 7
7 -> 11
11 -> 8
8 -> 2
2 -> 7
7 -> 6
6 -> 10
10 -> 4
4 -> 9
9 -> 11
11 -> 7
7 -> 8
8 -> 3
3 -> 9
9 -> 8
8 -> 11
11 -> 9
9 -> 10
10 -> 11
11 -> 6
6 -> 5
5 -> 0

solver.pl

#!/usr/bin/perl
use strict;
use warnings;
use feature ':5.10';
use List::Util qw(first max maxstr min minstr reduce shuffle sum);
use List::MoreUtils qw/:all/;
use Data::Dumper;

sub debug {
    #say STDERR @_;
}

my %verts;
my %edges;
sub edge_key {
    my ($i, $j) = sort { $a <=> $b } @_;
    return "$i-$j";
}
sub build_edge ($$) {
    my ($i, $j) = @_;
    die "Can't add an edge from a vertex to itself" if $i eq $j;
    $verts{$_} //= [] for @_;
    push @{$verts{$i}}, $j;
    push @{$verts{$j}}, $i;
    $edges{edge_key($i,$j)} = 0;
}
sub mod_edge {
    my ($i, $j, $val) = @_;
    my $key = edge_key($i,$j);
    my $cur = $edges{$key};
    debug "mod $key($cur) by $val";
    $edges{$key} += $val;
}
sub edge_count {
    $edges{edge_key(@_)};
}
sub fetch_near ($) {
    my ($n) = @_;
    return @{$verts{$n}};
}
sub fetch_first {
    return (sort {$a <=> $b} keys %verts)[0];
}
sub done {
    return all { $edges{$_} == 2 } keys %edges;
}

#-----------------------------------------------------
#for (qw/1-2 1-3 1-4 2-3 3-4 2-4/) {
for (qw/0-1 0-2 0-3 0-4 0-5 1-2 2-3 3-4 4-5 5-1 1-6 1-7 2-7 2-8 3-8 3-9 4-9 4-10 5-10 5-6 6-7 7-8 8-9 9-10 10-6 6-11 7-11 8-11 9-11 10-11/) {
    my ($x,$y) = split /-/;
    build_edge($x,$y);
}

sub search {
    my ($cur,$state) = @_;
    debug "Handling node $cur";
    return(1,[]) if done;
    my @n = sort { edge_count($cur, $a) <=> edge_count($cur, $b) } fetch_near($cur);
    return(0) if all { edge_count($cur,$_) >= 2 } @n;
    my $stretch = (grep { edge_count($cur,$_) > 0 } @n) > 1
        ? (minmax($state->{'stretch'},2))[1]
        : $state->{'stretch'};
    return(0) if $stretch <= 0;
    for (@n) {
        next if ($state->{'prev'} // '') eq $_;
        next if edge_count($cur,$_) >= 2;
        mod_edge($cur,$_,1);
        my ($success, $extra) = search($_, {
                prev => $cur,
                stretch => $stretch - 1,
            });
        if ($success) {
            unshift(@$extra, "$cur -> $_");
            return ($success, $extra);
        }
        else {
            mod_edge($cur,$_,-1);
            next
        }
    }
    return(0);
}

my $first = fetch_first;
my ($succ, $log) = search($first, {stretch=>3});

if ($succ) {
    say "digraph foo {";
    say "$_;" for @$log;
    say "}";
}
else {
    say "Could not find a valid solution";
}