Quatro cidades A, B, C e D estão ligadas por sSeis...

python
# Let's enumerate Euler trails of the multigraph with vertices A,B,C,D and edges:
# AB (1), AC (1), BC (1), CD (1), BD (2)
from collections import defaultdict

vertices = ['A','B','C','D']

# edges as list of (u,v,label)
edges = [
    ('A','B','AB'),
    ('A','C','AC'),
    ('B','C','BC'),
    ('C','D','CD'),
    ('B','D','BD1'),
    ('B','D','BD2'),
]

# adjacency list mapping node to list of edge indices that touch it
adj = defaultdict(list)
for i,(u,v,lbl) in enumerate(edges):
    adj[u].append(i)
    adj[v].append(i)

# helper to get the other endpoint
def other(i, u):
    a,b,lbl = edges[i]
    return b if a==u else a

# enumerate Euler trails starting at a given start vertex
def euler_trails_from(start):
    n = len(edges)
    used = [False]*n
    res = []
    path_vertices = [start]
    path_edges = []
    def dfs(u, used_count):
        if used_count == n:
            res.append((path_vertices.copy(), path_edges.copy()))
            return
        # explore edges from u not used yet
        for i in adj[u]:
            if not used[i]:
                used[i] = True
                path_edges.append(i)
                v = other(i,u)
                path_vertices.append(v)
                dfs(v, used_count+1)
                path_vertices.pop()
                path_edges.pop()
                used[i] = False
    dfs(start, 0)
    return res

trails_C = euler_trails_from('C')
trails_D = euler_trails_from('D')
len(trails_C), len(trails_D)

(16, 16)

python
def trail_endpoints(trails):
    ends = set()
    for pv,pe in trails:
        ends.add(pv[-1])
    return ends

trail_endpoints(trails_C), trail_endpoints(trails_D)

({'D'}, {'C'})