Euler Path & Circuit Finder

Find Eulerian paths and circuits in graphs. Determine if a graph has an Eulerian trail or cycle using graph theory algorithms.

Eulerian Graph Theory: An Eulerian path visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Euler's Theorem: A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian path (not circuit) if and only if exactly two vertices have odd degree.
Enter one edge per line. For weighted graphs, add weight as third number.
Graph Drawing Tools
0
Vertices
0
Edges
Königsberg Bridges
The classic 7 bridges problem
No Euler Path
Complete Graph K₅
All vertices connected
Euler Circuit
Cycle Graph C₆
Simple cycle with 6 vertices
Euler Circuit
Path Graph P₄
Simple path with 4 vertices
Euler Path
Star Graph S₅
Central vertex connected to others
No Euler Path
Custom Graph
Create your own graph
Custom

Understanding Euler Paths & Circuits

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once. An Eulerian circuit (or Eulerian cycle) is an Eulerian trail that starts and ends on the same vertex.

Historical Context: The concept originates from the Seven Bridges of Königsberg problem, solved by Leonhard Euler in 1736, which laid the foundations of graph theory.

Euler's Theorems

1

For Undirected Graphs:

  • A connected graph has an Eulerian circuit if and only if every vertex has even degree.
  • A connected graph has an Eulerian path (not circuit) if and only if exactly two vertices have odd degree.
  • If a graph has more than two vertices of odd degree, it has no Eulerian path or circuit.
2

For Directed Graphs:

  • A directed graph has an Eulerian circuit if and only if it is strongly connected and each vertex has equal in-degree and out-degree.
  • A directed graph has an Eulerian path if and only if it is strongly connected and at most one vertex has (out-degree − in-degree) = 1, at most one vertex has (in-degree − out-degree) = 1, and all other vertices have equal in-degree and out-degree.

Algorithms

1

Hierholzer's Algorithm (1873):

  1. Find a random cycle in the graph
  2. While there are unused edges:
    • Find a vertex on the current cycle with unused edges
    • Find a new cycle starting from that vertex
    • Merge the new cycle into the current cycle

Time complexity: O(|E|) where E is the number of edges.

2

Fleury's Algorithm (1883):

  1. Start at a vertex of odd degree (if exists) or any vertex
  2. While there are edges remaining:
    • Identify bridges in the current graph
    • Choose an edge that is not a bridge (unless no other option)
    • Add the edge to the path and remove it from the graph
    • Move to the next vertex

Time complexity: O(|E|²) where E is the number of edges.

Applications

  • DNA Fragment Assembly: Eulerian paths in de Bruijn graphs
  • Route Planning: Chinese Postman Problem (shortest route covering all streets)
  • Circuit Board Testing: Ensuring all connections are tested
  • Network Analysis: Analyzing connectivity and flow in networks
  • Puzzle Solving: Solving maze and drawing puzzles

Calculator Features:

  • Multiple input methods: adjacency matrix, edge list, and interactive drawing
  • Supports both undirected and directed graphs
  • Implements both Hierholzer's and Fleury's algorithms
  • Visualizes the graph with highlighted Euler path/circuit
  • Step-by-step execution for learning and debugging
  • Checks all Eulerian conditions and provides detailed analysis
  • Export results as PNG or JSON
  • Compare algorithm performance

Frequently Asked Questions

An Euler path visits every edge exactly once, while a Hamiltonian path visits every vertex exactly once. Finding an Euler path can be done in polynomial time, while finding a Hamiltonian path is NP-complete.

No, a disconnected graph cannot have an Euler path or circuit (except in the trivial case where all components except one are isolated vertices). The graph must be connected (or weakly connected for directed graphs) for an Eulerian trail to exist.

Hierholzer's algorithm is more efficient with O(|E|) time complexity, while Fleury's algorithm is O(|E|²). However, Fleury's algorithm is simpler to understand and implement, making it better for educational purposes. This tool implements both algorithms.

Count the vertices with odd degree. If all vertices have even degree, the graph has an Euler circuit. If exactly two vertices have odd degree, it has an Euler path (but not circuit). If any other number of vertices have odd degree, it has neither.

Yes, a graph can have multiple distinct Eulerian paths or circuits. The number depends on the graph's structure. For example, a complete graph with n vertices (where n is odd) has (n-1)! distinct Eulerian circuits.