Checking Eulerian Conditions

Before finding an Euler path, verify the conditions:

function isEulerian(graph):
    oddCount = 0
    for each vertex v:
        if degree[v] is odd:
            oddCount = oddCount + 1

    if oddCount == 0:
        return "Euler circuit exists"
    else if oddCount == 2:
        return "Euler path exists"
    else:
        return "No Euler path"

For directed graphs, check in-degree vs out-degree instead.

Time: $O(V)$ to count degrees. You must also verify connectivity with DFS/BFS.

Space complexity is $O(E)$ for the data structures used.