Eulerian circuit

A thorough tour of all a graph's edges that ends where it started.

An Eulerian circuit is a walk that uses each edge in a connected graph exactly once and loops back to the starting vertex. Graphs that have Eulerian circuits are Eulerian.

It's okay for Eulerian circuits to repeat vertices, they're not necessarily paths.

A graph has an Eulerian circuit if and only if it is a single connected component and all of its vertices have even degree.

Therefore, if any vertex in a graph has odd degree, then that graph cannot have an Eulerian circuit. This is because trying to use all the edges incident to that vertex exactly once leads to a situation where the vertex cannot be left.

Here's an algorithm that finds an Eulerian circuit in a graph:

algorithm find_eulerian_circuit is
    input: a connected graph G = (V, E) whose vertices all have even degree
    output: an Eulerian circuit (a sequence of edges)

    C ← find_circuit(G)
    while there exists an edge in G not in C
        let G' be a copy of G
        remove all edges from G' that are already in C
        remove all isolated vertices from G'
        let w be any vertex that G' and C share
        C' ← find_circuit(G') (circuit must start with w)
        insert the contents of C' into C immediately after the edge in C that leads to w
    return C

By maintaining the properties of a circuit through each iteration and continually adding edges, this algorithm ensures that an Eulerian circuit will eventually be achieved. Every time the loop runs, the circuit gets closer to touring every edge.