An Eulerian Path in a graph is a trail that visits every edge exactly once. If such a path exists and starts and ends at the same vertex, it is called an Eulerian Circuit. These concepts are fundamental in graph theory, providing insights into network traversal problems.

Eulerian Path: Conditions

For a graph to have an Eulerian Path, it should have exactly 0 or 2 vertices of odd degree. If there are 0 odd degree vertices, the path is also an Eulerian Circuit.

Eulerian Circuit: Conditions

A graph has an Eulerian Circuit if all vertices have even degrees. This ensures the path starts and ends at the same vertex.


import java.util.*;

class Graph {
    private int V; // No. of vertices
    private LinkedList adj[]; // Adjacency list

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v); // Undirected graph
    }

    boolean isEulerian() {
        int odd = 0;
        for (int i = 0; i < V; i++)
            if (adj[i].size() % 2 != 0)
                odd++;

        return (odd == 0 || odd == 2);
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 0);
        g.addEdge(2, 4);

        if (g.isEulerian())
            System.out.println("Graph has an Eulerian Path");
        else
            System.out.println("Graph does not have an Eulerian Path");
    }
}

Example 1: Simple Graph

In this example, we create a simple graph with 5 vertices and check if it has an Eulerian Path. The graph has two vertices of odd degree, hence it has an Eulerian Path.

Example 2: Complete Circuit

Consider a complete circuit graph where each vertex connects to every other vertex. This graph will have an Eulerian Circuit since all vertices have even degrees.

Console Output:

Graph has an Eulerian Path

Example 3: Directed Graph

Directed Eulerian Path

For directed graphs, an Eulerian Path exists if exactly one vertex has (outdegree - indegree) = 1, exactly one vertex has (indegree - outdegree) = 1, and all other vertices have equal in and out degrees.


import java.util.*;

class DirectedGraph {
    private int V;
    private LinkedList adj[];

    DirectedGraph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    boolean isEulerianPath() {
        int start = 0, end = 0;
        for (int i = 0; i < V; i++) {
            int out = adj[i].size();
            int in = 0;
            for (int j = 0; j < V; j++)
                if (adj[j].contains(i))
                    in++;

            if (out - in == 1)
                start++;
            else if (in - out == 1)
                end++;
            else if (in != out)
                return false;
        }
        return (start == 1 && end == 1);
    }

    public static void main(String args[]) {
        DirectedGraph dg = new DirectedGraph(4);
        dg.addEdge(0, 1);
        dg.addEdge(1, 2);
        dg.addEdge(2, 3);
        dg.addEdge(3, 0);

        if (dg.isEulerianPath())
            System.out.println("Directed Graph has an Eulerian Path");
        else
            System.out.println("Directed Graph does not have an Eulerian Path");
    }
}

Example 3: Directed Graph

This example demonstrates a directed graph with a valid Eulerian Path. The conditions for a directed Eulerian Path are checked, ensuring the graph traversal covers all edges exactly once.

Console Output:

Directed Graph has an Eulerian Path

Example 4: Disconnected Graph

Eulerian Path in Disconnected Graphs

A disconnected graph cannot have an Eulerian Circuit. However, it might have an Eulerian Path if the connected components satisfy the path conditions independently.


import java.util.*;

class DisconnectedGraph {
    private int V;
    private LinkedList adj[];

    DisconnectedGraph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isConnected() {
        boolean visited[] = new boolean[V];
        Arrays.fill(visited, false);

        int i;
        for (i = 0; i < V; i++)
            if (adj[i].size() != 0)
                break;

        if (i == V)
            return true;

        DFSUtil(i, visited);

        for (i = 0; i < V; i++)
            if (visited[i] == false && adj[i].size() > 0)
                return false;

        return true;
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        for (int n : adj[v])
            if (!visited[n])
                DFSUtil(n, visited);
    }

    boolean isEulerian() {
        if (!isConnected())
            return false;

        int odd = 0;
        for (int i = 0; i < V; i++)
            if (adj[i].size() % 2 != 0)
                odd++;

        return (odd == 0 || odd == 2);
    }

    public static void main(String args[]) {
        DisconnectedGraph dg = new DisconnectedGraph(5);
        dg.addEdge(0, 1);
        dg.addEdge(1, 2);
        dg.addEdge(3, 4);

        if (dg.isEulerian())
            System.out.println("Disconnected Graph has an Eulerian Path");
        else
            System.out.println("Disconnected Graph does not have an Eulerian Path");
    }
}

Example 4: Disconnected Graph

This example illustrates a disconnected graph. The graph is checked for connectivity and the Eulerian Path conditions. A disconnected graph typically does not support an Eulerian Circuit.

Console Output:

Disconnected Graph does not have an Eulerian Path

Example 5: Complex Graph with Multiple Components

Complex Graph Analysis

A complex graph with multiple components can be analyzed for Eulerian paths and circuits by evaluating each component separately. The overall graph must be connected for an Eulerian Circuit.


import java.util.*;

class ComplexGraph {
    private int V;
    private LinkedList adj[];

    ComplexGraph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isEulerian() {
        int odd = 0;
        for (int i = 0; i < V; i++)
            if (adj[i].size() % 2 != 0)
                odd++;

        return (odd == 0 || odd == 2);
    }

    public static void main(String args[]) {
        ComplexGraph cg = new ComplexGraph(6);
        cg.addEdge(0, 1);
        cg.addEdge(1, 2);
        cg.addEdge(2, 0);
        cg.addEdge(3, 4);
        cg.addEdge(4, 5);
        cg.addEdge(5, 3);

        if (cg.isEulerian())
            System.out.println("Complex Graph has an Eulerian Path");
        else
            System.out.println("Complex Graph does not have an Eulerian Path");
    }
}

Example 5: Complex Graph

This example analyzes a complex graph with multiple components. Each component is evaluated for Eulerian Path conditions, highlighting the need for comprehensive connectivity in Eulerian Circuits.

Console Output:

Complex Graph does not have an Eulerian Path