Euler Path | Euler Cicruit | Euler Graph

Notes from studying about Euler Path

What is Euler Path?

If we visit all the edges of a graph only once, then the path that we traversed is called the Euler path. We need to choose the start node carefully, otherwise we cannot get an euler path. Also not all the graphs have euler path.

Eulerian Circuit

A Eulerian path that starts and ends at the same node, is called Eulerian circuit. A graph which has an eulerian circuit, the path can be started from any node in that circuit. For a graph to have Euler path or circuit, all the nodes with non-zero degree should be part of a single connected component in the graph. All vertices if they have even degrees, then the graph can have Eulerian circuit.

A graph which has Eulerian path but not eulerian circuit, is called Semi-Eulerian graph. For this graph start and end vertext will have odd degrees. A graph which has both Eulerian path and Eulerian circuit is called Eulerian Graph.

To check if a graph has Eulerian circuit we will check the below things -

• Check if graph is connected using DFS and starting from a non-zero degree vertex, if not then no eulerian path or cirucit

• If it is connected then check the degree of the vertices, it should be even for a graph to have eulerian circuit.

A simple code approach to find if a graph has Eulerian cycle or code is given below -

// Problem Link: https://www.geeksforgeeks.org/problems/euler-circuit-and-path/1?ref=gcse_outind
import java.util.*;

class Solution {
    public int isEulerCircuit(int n, List<Integer>[] adj) {
        // Check if the graph is connected
        if (!isConnected(n, adj))
            return 0;

        // Count vertices with odd degrees
        int oddDegreeVertices = 0;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() % 2 == 1) {
                oddDegreeVertices++;
            }
        }

        if (oddDegreeVertices > 2) {
            return 0; // Not an Eulerian path or circuit
        }
        if (oddDegreeVertices == 2) {
            return 1; // Eulerian path (but not circuit)
        }
        return 2; // Eulerian circuit
    }

    private boolean isConnected(int n, List<Integer>[] adj) {
        int nonzeroVertex = -1;

        // Get the first non-zero degree vertex
        for (int i = 0; i < n; i++) {
            if (!adj[i].isEmpty()) {
                nonzeroVertex = i;
                break;
            }
        }

        if (nonzeroVertex == -1) {
            return false; // No edges in the graph
        }

        boolean[] visited = new boolean[n];

        // Start DFS from this vertex
        dfs(nonzeroVertex, visited, adj);

        // If any vertex with non-zero degree is not visited, the graph is not connected
        for (int i = 0; i < n; i++) {
            if (!visited[i] && !adj[i].isEmpty()) {
                return false;
            }
        }

        return true;
    }

    private void dfs(int node, boolean[] visited, List<Integer>[] adj) {
        visited[node] = true;

        for (int i = 0; i < adj[node].size(); i++) {
            int curr = adj[node].get(i);
            if (!visited[curr]) {
                dfs(curr, visited, adj);
            }
        }
    }
}

Euler Path in Directed Graphs

For a graph to have Eulerian path, it will have below properties for its nodes -

• source node - Indegree[node]-Outdegree[node] = 1

• dest node - Outdegree[node]-Indegree[node] = 1

• for all the other nodes - Indegree[node] = outdegree[node]

To solve any problem related to Euler path in directed graphs, start with finding the source node.

If all the nodes have same indegree and outdegree then that graph will have a Eulerian Circuit. And this graph any node can be the start node.

That was all for the notes.