Pense por mais tempo: Quatro cidades A, B, C e D e...

python
# Let's count Euler trails in undirected multigraph with parallel edges.
from collections import defaultdict

nodes = ['A','B','C','D']
edges = [('A','B','AB'),
         ('A','C','AC'),
         ('B','C','BC'),
         ('B','D','BD1'),
         ('B','D','BD2'),
         ('C','D','CD')]

# Represent as list of edges with ids to remove when used.
edge_list = edges

# Adjacency mapping from node to list of edges (index)
adj = defaultdict(list)
for i,(u,v,lab) in enumerate(edge_list):
    adj[u].append(i)
    adj[v].append(i)

N = len(edge_list)

def other(i, u):
    a,b,lab = edge_list[i]
    return b if u==a else a

count_CD = 0
paths = []

def backtrack(u, used, path_vertices, used_edges):
    # u is current node, used is count of used edges
    global count_CD
    if used == N:
        # must end at D if started at C; check path start
        if path_vertices[0] == 'C' and u == 'D':
            count_CD += 1
            paths.append(path_vertices.copy())
        return
    # try all unused edges incident to u
    for i in adj[u]:
        if i not in used_edges:
            used_edges.add(i)
            v = other(i,u)
            path_vertices.append(v)
            backtrack(v, used+1, path_vertices, used_edges)
            path_vertices.pop()
            used_edges.remove(i)

# start at 'C'
backtrack('C', 0, ['C'], set())
count_CD, len(paths)


(16, 16)