Euler's Painting Duality

As is well-known, there are $\boxed{60}$ directed Hamiltonian cycles on the dodecaheadral graph (which is the graph of the faces of an icosahedron).

Because I don't know python, I resorted to a language that I do know. C. Great fun. Basically, it's a depth first graph search. (Note that everything is zero based and the fourth element in each array is the marker needed for the search algorithm.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>

int adjs[20][4] = {
    {6, 12, 18, 0},
    {11, 17, 19, 0},
    {15, 16, 18, 0},
    {10, 13, 17, 0},
    {12, 14, 17, 0},
    {8, 13, 15, 0},
    {0, 14, 16, 0},
    {9, 15, 19, 0},
    {5, 10, 18, 0},
    {7, 11, 16, 0},
    {3, 8, 12, 0},
    {1, 9, 14, 0},
    {0, 4, 10, 0},
    {3, 5, 19, 0},
    {4, 6, 11, 0},
    {2, 5, 7, 0},
    {2, 6, 9, 0},
    {1, 3, 4, 0},
    {0, 2, 8, 0},
    {1, 7, 13, 0}
};
int count = 0;

void path(int f, int pl)
{
    int i;

    if (adjs[f][3] == 1)
    {
        if (pl == 20 && f == 0)
        {
            count++;
        }
        return;
    }

    adjs[f][3] = 1;
    for (i = 0; i < 3; i++)
    {
        path(adjs[f][i], pl + 1);
    }
    adjs[f][3] = 0;
}

int main(int argc, char **argv)
{
    path(0, 0);
    printf("Found %d paths\n", count);
}

This is a classic Hamiltonian Cycles problem. I used the following code in Python 3 to solve:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

adjacencies = {
1 : [7, 13, 19], 2 : [12, 18, 20], 3 : [16, 17, 19], 4 : [11, 14, 18],
5 : [13, 15, 18], 6 : [9, 14, 16], 7 : [1, 15, 17], 8 : [10, 16, 20],
9 : [6, 11, 19], 10 : [8, 12, 17], 11 : [4, 9, 13], 12 : [2, 10, 15],
13 : [1, 5, 11], 14 : [4, 6, 20], 15 : [5, 7, 12], 16 : [3, 6, 8],
17 : [3, 7, 10], 18 : [2, 4, 5], 19 : [1, 3, 9], 20 : [2, 8, 14]
}

#Constructing Hamiltonian paths between two points
def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
              if len(newpath)==len(graph):
                  paths.append(newpath)
    return paths

set=[]
for i in adjacencies[1]:
    set.append(find_all_paths(adjacencies, 1, i))

print(len([j for i in set for j in i]))

This outputs the answer as $\boxed{60}$ .

A simple, inefficient python solution. It completes a depth first search of all possible walks then checks if the last step was adjacent to the starting face.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

adj = {
1 : [7, 13, 19], 2 : [12, 18, 20], 3 : [16, 17, 19], 4 : [11, 14, 18],
5 : [13, 15, 18], 6 : [9, 14, 16], 7 : [1, 15, 17], 8 : [10, 16, 20],
9 : [6, 11, 19], 10 : [8, 12, 17], 11 : [4, 9, 13], 12 : [2, 10, 15],
13 : [1, 5, 11], 14 : [4, 6, 20], 15 : [5, 7, 12], 16 : [3, 6, 8],
17 : [3, 7, 10], 18 : [2, 4, 5], 19 : [1, 3, 9], 20 : [2, 8, 14]
}

count = 0

def walk(steps):
    global count

    #When we get to step 20, we can check if the last step was adjacent to the starting face
    if len(steps) == 20:
        if steps[-1] in adj[1]:
            count += 1
        return

    #Otherwise recursively call walk for the sides adjacent to the
    #last step that we haven't already walked across 
    for n in adj[steps[-1]]:
        if n not in steps:
            new_steps = steps[:]
            new_steps.append(n)
            walk(new_steps)

walk([1])
print(count)

There will be $\boxed{60}$ Hamilton cycles.