Introduction to Eulerian Paths and Circuits

Definition

An Eulerian path is a trail in a graph that traverses every edge exactly once. A trail means that no edge is repeated, although vertices may be repeated.

An Eulerian circuit (also called an Eulerian cycle) is an Eulerian path that starts and ends at the same vertex.

Key conditions for a connected graph:

A graph has an Eulerian circuit if and only if every vertex has even degree.
A graph has an Eulerian path but not a circuit if and only if exactly two vertices have odd degree.
If more than two vertices have odd degree, then the graph has neither an Eulerian path nor an Eulerian circuit.

Important notes:

The graph must be connected, except possibly for isolated vertices that do not affect the trail.
The concept applies to undirected graphs in the standard introductory form.
In directed graphs, similar conditions exist, but they depend on in-degree and out-degree.

Main Content

1. Eulerian Path

An Eulerian path is a route through a graph that uses each edge exactly once, but it does not need to end where it started.
A connected graph has an Eulerian path precisely when it contains exactly two vertices of odd degree. These are the start and end vertices of the path.

Explanation:

To understand why odd-degree vertices matter, remember that each time you enter a vertex by one edge, you usually leave by another edge. So edges are naturally paired at each internal vertex. This pairing works perfectly for vertices with even degree. If a graph has exactly two odd-degree vertices, then those two vertices can serve as the beginning and ending of the trail, leaving one unmatched edge at each end.

Example:

Consider the graph with vertices and edges:

Vertices: A, B, C, D
Edges: AB, BC, CD, DA, AC

Degrees:

deg(A) = 3
deg(B) = 2
deg(C) = 3
deg(D) = 2

Here, exactly two vertices (A and C) have odd degree, so an Eulerian path exists. One possible Eulerian path is:

A → B → C → D → A → C

This uses every edge exactly once.

2. Eulerian Circuit

An Eulerian circuit is a closed trail that uses every edge exactly once and ends at the same vertex where it began.
A connected graph has an Eulerian circuit precisely when all vertices have even degree.

Explanation:

If every vertex has even degree, then every time the trail enters a vertex, it can also leave it using another unused edge. This makes it possible to continue until returning to the starting point without getting stuck prematurely. Since there are no odd-degree vertices, there is no “unfinished” edge at any vertex.

Example:

Take a square graph with vertices A, B, C, D and edges AB, BC, CD, DA.

Degrees:

deg(A) = 2
deg(B) = 2
deg(C) = 2
deg(D) = 2

All degrees are even, so the graph has an Eulerian circuit. One such circuit is:

A → B → C → D → A

This starts and ends at A and uses each edge exactly once.

Why it matters:

Eulerian circuits are especially useful in tasks where a route must return to the starting point, such as:

street cleaning routes
postal delivery loops
inspection tours of networks
plotting closed routes in maps or diagrams

3. Degree Conditions and Graph Characterization

The degree of a vertex is the number of edges incident to it, and it is the most important factor in determining whether a graph has an Eulerian path or circuit.
The existence of Eulerian paths and circuits depends on the parity of vertex degrees:
0 odd vertices → Eulerian circuit exists
2 odd vertices → Eulerian path exists
more than 2 odd vertices → neither exists

Detailed reasoning:

At every intermediate vertex of a trail, each arrival must be matched with a departure, so the trail contributes edges in pairs. This means internal vertices require even degree. Only the starting and ending vertices can have one extra “unpaired” edge, which is why at most two odd-degree vertices are allowed for an Eulerian path.

Small illustration of degree parity:

Consider this graph:

Vertices: P, Q, R, S
Edges: PQ, QR, RS, SP, PR

Degrees:

deg(P) = 3
deg(Q) = 2
deg(R) = 3
deg(S) = 2

Since there are exactly two odd vertices (P and R), there is an Eulerian path but no Eulerian circuit.

ASCII-style visual example for a graph with an Eulerian circuit:

A ----- B
|       |
|       |
D ----- C

Possible circuit: A → B → C → D → A

ASCII-style visual example for a graph with an Eulerian path:

A ----- B
 \     /
  \   /
    C

Possible Eulerian path: A → B → C → A

(Here, the actual edge set matters; the diagram is only for conceptual understanding.)

Working / Process

1. Check whether the graph is connected

First, ensure that all non-isolated vertices belong to one connected component.
If the graph is disconnected, an Eulerian path or circuit is generally impossible because you cannot traverse all edges in one continuous trail.

2. Count the degree of every vertex

Compute how many edges meet at each vertex.
Identify vertices with odd degree and vertices with even degree.
This step is the key to deciding the type of Eulerian traversal.

3. Apply the Eulerian conditions

If all vertices have even degree, conclude that an Eulerian circuit exists.
If exactly two vertices have odd degree, conclude that an Eulerian path exists.
If the graph has more than two odd-degree vertices, conclude that neither exists.

Practical construction method: Fleury’s Algorithm

If you want to actually build an Eulerian trail, one common method is Fleury’s Algorithm:

Start at a valid vertex:
any vertex if finding a circuit
one of the odd-degree vertices if finding a path
Choose an edge that is not a bridge unless necessary.
Remove the used edge from the graph.
Continue until all edges are used exactly once.

Another construction idea: Hierholzer’s Algorithm

This is a more efficient method:

Start at a suitable vertex.
Follow edges until you return to the starting point or get stuck.
If unused edges remain, form and merge additional cycles.
Continue until all edges are included.

This algorithm is widely used in computer science because it is faster and more practical for large graphs.

Advantages / Applications

Helps solve real-world route problems where every connection must be covered exactly once, such as garbage collection, mail delivery, snow plowing, and street sweeping.
Provides an elegant mathematical way to analyze graph structure using vertex degrees and connectivity.
Forms the basis for advanced algorithms in network design, optimization, and computer science, especially in routing and traversal problems.

Additional applications:

Puzzle solving

Many path-based puzzles are modeled using Eulerian trails.

DNA sequencing

Some sequence assembly problems use graph traversal ideas related to Eulerian paths.

Transport and logistics

Efficient routes can be designed by understanding whether a network supports an Eulerian traversal.

Circuit design and robotics

Closed inspection or movement routes can be planned using Eulerian circuits.

Summary

Eulerian paths and circuits describe traversals that use every edge exactly once.
A connected graph has an Eulerian circuit when all vertices have even degree.
A connected graph has an Eulerian path when exactly two vertices have odd degree.
These concepts are useful in route planning, optimization, and graph analysis.