Euler & Hamilton Paths

Traversal Problems

Euler Paths and Circuits

An Euler path visits every edge exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Euler's Theorem (1736, the Königsberg bridge problem):

• A connected graph has an Euler circuit iff every vertex has even degree.
• A connected graph has an Euler path (not circuit) iff exactly two vertices have odd degree.

The classic Königsberg bridge graph has four vertices of odd degree (3, 3, 3, 5) — no Euler path exists.

Hamilton Paths and Cycles

A Hamilton path visits every vertex exactly once. A Hamilton cycle returns to the start.

Unlike Euler, there is no simple degree condition for Hamilton paths. The problem is NP-complete in general (related to the Travelling Salesman Problem).

Dirac's theorem: If every vertex of a graph on $n \geq 3$ vertices has degree $\geq n/2$, a Hamilton cycle exists.

def has_euler_circuit(adj_list):
    return all(len(neighbors) % 2 == 0
               for neighbors in adj_list.values())

# Cycle C4: all degrees 2 → Euler circuit exists
C4 = {0: [1,3], 1: [0,2], 2: [1,3], 3: [2,0]}
print(has_euler_circuit(C4))  # True

Your Task

Implement has_euler_circuit, has_euler_path, and is_connected.