Lesson 5

The considered proof can be turned into an algorithm that finds an Eulerian cycle (or states its absence) in a given graph \(G(V,E)\) in time \(O(|V|+|E|)\).

The code below finds an Eulerian path through the bridges of Kaliningrad. The corresponding graph has parallel edges. For this reason, we use the \(\texttt{MultiGraph}\) class.

from networkx import MultiGraph, eulerian_path

g = MultiGraph(['AB', 'AC', 'BD', 'BC', 'CD', 'CD'])
print(*eulerian_path(g))

('B', 'A') ('A', 'C') ('C', 'B') ('B', 'D') ('D', 'C') ('C', 'D')