What Is a Euler Circuit? a Clear Guide for Students

Do not index

An Euler circuit is a closed walk through every edge exactly once, returning to where it started. In a connected graph, it exists if and only if every vertex has even degree.

You may be looking at a network diagram for class, trying to solve a route-planning puzzle, or preparing for a Model United Nations math round, and wondering whether one continuous journey can use every connection without repeating any. The answer doesn't come from guessing a clever route first. It comes from understanding the graph's structure, especially the number of edges meeting at each vertex.

The recurring picture in this guide is a person crossing bridges. That analogy makes the rule easier to remember, but the careful vocabulary matters just as much. A walk, trail, path, and circuit aren't interchangeable, and confusing them can turn a correct solution into an incorrect one. Once those terms are clear, the even-degree test, proof idea, construction algorithm, and directed-graph variation become much easier to follow.

The Königsberg Bridges and the Origin of Euler Circuits

In 18th-century Königsberg, seven bridges connected four land masses across the Pregel River. Residents asked whether someone could take a single stroll, cross every bridge exactly once, and return to the starting point.

The question sounds like a local walking challenge, but it contains the basic shape of a graph-theory problem. Treat each land mass as a vertex and each bridge as an edge. A successful stroll would need to use every edge once, while ending at its starting vertex.

Leonhard Euler studied the problem in 1735–1736, and his analysis is widely treated as the origin of graph theory and one of its first major theorems. Euler showed that crossing each of the 7 bridges exactly once without repeating was impossible, which transformed a practical routing puzzle into a general mathematical rule. You can read more about the broader idea of how patterns recur in history through this discussion of history repeating itself.

The formal definition

An Euler circuit is a closed trail that uses every edge exactly once and returns to its starting vertex. “Closed” means that the journey ends where it began. “Trail” means that no edge is repeated, although a vertex may be visited more than once.

That last distinction often surprises beginners. Suppose you enter a land mass, leave by another bridge, later return to it, and depart again. You've repeated a vertex, but you haven't repeated an edge. That can be perfectly valid in an Euler circuit.

The Königsberg problem also reveals why the answer depends on edge arrangements rather than on the visual size of the map. The city had 4 land masses and 7 bridges, but the decisive issue was how many bridges touched each land mass. Euler's criterion is precise: a connected graph has an Euler circuit if and only if every vertex has even degree. That rule still anchors introductory graph theory because it lets you test feasibility before trying to draw a route.

Walks, Trails, Paths, and Circuits Clearly Distinguished

The phrase “visit every edge once” isn't enough to identify an Euler circuit. Graph theory uses several related terms, and each one imposes a different restriction.

A walk is the broadest category. You may repeat vertices and edges. If you cross the same bridge, return to the same land mass, and cross that bridge again, you've still taken a walk.

A trail is a walk that doesn't repeat edges. Vertices may still repeat because you can arrive at the same location through different edges.

A path usually forbids repeated vertices. Since repeated vertices are prohibited, repeated edges are also excluded. A path is therefore more restrictive than a trail.

A circuit is a closed trail. It begins and ends at the same vertex, while still avoiding repeated edges. An Euler circuit adds one further requirement, it must include every edge in the graph exactly once. An Euler path uses every edge exactly once but doesn't need to return to its starting vertex.

A small bridge map

Consider a graph with vertices A, B, C, D, and edges AB, BC, CD, DA, AC. A traversal such as A-B-C-A-D-A repeats the vertex A, so it isn't a simple path. It may still be a trail if no edge appears twice.

The classification ladder looks like this:

Term	Edges may repeat?	Vertices may repeat?	Must end at start?
Walk	Yes	Yes	No
Trail	No	Yes	No
Path	No	No	No
Circuit	No	Yes	Yes
Euler path	No, and every edge is used	Possibly	No
Euler circuit	No, and every edge is used	Possibly	Yes

The most common exam mistake is calling any edge-covering route an Euler circuit. Check the endpoint condition separately. If the route uses every edge once but ends at a different vertex, it's an Euler path, not an Euler circuit.

For a more general review of formal mathematical notation and related definitions, see this guide to mathematical sets and notation.

The Even-Degree Rule and Why It Works

The degree of a vertex is the number of edges meeting it. In the bridge analogy, it's the number of bridges connected to a land mass.

For an undirected graph, the test is:

Confirm that the graph is connected, ignoring isolated vertices that have no edges.

Count the degree of every vertex.

Check that every degree is even.

Only then construct a route.

Why does an even number matter? Every time your route arrives at a vertex during a closed journey, it must later leave that vertex. Arrival and departure consume edges in pairs. A vertex with degree 2 can support one arrival and one departure. A vertex with degree 4 can support two such pairings. The same logic extends to any even degree.

Consider a connected graph shaped as a square, with vertices A, B, C, and D and edges AB, BC, CD, and DA. Each vertex has degree 2. A-B-C-D-A uses every edge once and returns to A, so it's an Euler circuit.

Now add a diagonal edge AC. The degrees change: A and C each gain one additional incident edge, so both become odd. The graph remains connected, but no closed route can use every edge exactly once. At A and C, one edge would be left unmatched between arrivals and departures.

Connectivity matters too. A graph could have every vertex with even degree while containing separate edge-bearing components. A single traveler can't cross from one disconnected component to another, so no single Euler circuit can cover all the edges.

The criterion is both necessary and sufficient, not merely a useful hint. If a connected graph has an Euler circuit, all degrees must be even. If a connected graph has only even-degree vertices, an Euler circuit can be constructed. This makes degree counting the fastest practical diagnostic before route-building, as explained in this treatment of Euler circuits/12:_Graph_Theory/12.05:_Euler_Circuits).

A Proof Sketch You Can Actually Follow

The theorem has two directions. First, every Euler circuit must satisfy the even-degree condition. Second, a connected graph whose vertices all have even degree must contain such a circuit.

Why even degrees are necessary

Start with a completed Euler circuit. At the starting vertex, the route uses one edge to leave and another edge to return. At every other vertex visited along the way, each arrival must be matched by a departure.

You can think of every visit as consuming two edge incidences, one entering and one leaving. Because the circuit uses every edge, no edge can remain unmatched at the end. Therefore, every vertex has an even number of incident edges.

This argument also explains why a closed route can't pass through a vertex with an odd degree while using all its edges exactly once. At some point, one edge would have no partner for an arrival or departure.

Why even degrees are sufficient

Now suppose a connected graph has only even-degree vertices. Begin at any vertex and follow unused edges. Because each time you enter a vertex there are enough unused edges to leave again, you can't get stuck at a different vertex. Eventually, you return to your starting point and form a closed trail.

That first circuit may not include every edge. If unused edges remain, connectivity ensures that some vertex on the existing circuit is incident to an unused edge. Start there and follow unused edges again. The same even-degree pairing argument produces another closed circuit.

Insert, or splice, the new circuit into the old one at their shared vertex. Repeat until no unused edges remain. The resulting closed trail uses every edge exactly once.

This constructive reasoning resembles the way you might combine smaller loops in a telescoping series. The key difference is that graph edges are being consumed and circuits are being joined, rather than algebraic terms cancelling.

A quick self-check: if a connected graph has one vertex of degree 3 and another of degree 5, can it have an Euler circuit? No. Both odd degrees violate the necessary condition, regardless of how attractive a proposed route looks.

Hierholzer's Algorithm With a Worked Example

Once the degree test says a circuit exists, Hierholzer's algorithm constructs one by growing and splicing closed routes. Use a five-vertex graph with vertices A, B, C, D, and E, and edges:

AB, BC, CD, DE, EA, AC, CE, EB

The graph is connected, and every vertex has even degree. One possible count is A with degree 4, B with degree 4, C with degree 4, D with degree 2, and E with degree 4.

The route-building process

Start at A and follow unused edges:

Take AB.

Take BC.

Take CD.

Take DE.

Take EA.

This produces the closed circuit A-B-C-D-E-A. Several edges remain unused, including AC, CE, and EB.

Vertex C lies on the existing circuit and still touches unused edges. Start a new unused-edge circuit at C:

Take CE.

Take EB.

Take BA would repeat AB, so don't use it.

This particular choice exposes an important practical point. The remaining unused-edge subgraph must be followed carefully, and the algorithm's stack procedure prevents you from prematurely committing to an invalid continuation. A cleaner edge set for demonstration is to use the first cycle A-B-C-D-E-A and remaining edges AC, CE, EA. Those remaining edges form C-E-A-C, a closed circuit.

Splice C-E-A-C into the first circuit at C. Replace the occurrence of C in A-B-C-D-E-A with the new loop:

A-B-C-E-A-C-D-E-A

Every listed edge appears once. The route returns to A, so it's an Euler circuit.

Stack-style pseudocode in plain language

A practical implementation keeps a stack:

Push a starting vertex.

While the top vertex has an unused incident edge, remove that edge and push the neighboring vertex.

When the top vertex has no unused edges, pop it and add it to the circuit.

Read the resulting circuit in reverse construction order.

This approach handles splicing automatically. It also avoids the main weakness of Fleury's algorithm, which repeatedly asks whether choosing an edge would create a premature bridge. Hierholzer focuses on consuming edges and assembling closed cycles instead.

Aspect	Hierholzer's Algorithm	Fleury's Algorithm
Main idea	Build closed circuits and splice them	Choose edges while avoiding premature bridges
Decision process	Uses unused edges through a stack	Tests whether an edge is safe before taking it
Manual use	Efficient after degree and connectivity checks	Intuitive for small diagrams
Implementation	Well suited to systematic construction	Can require repeated bridge checks

The algorithm is commonly described as having linear time in the size of the graph, meaning its work scales with the graph's vertices and edges rather than requiring a fresh global search after every move. For hand-solving, remember the three verbs: follow, close, splice.

Directed Graphs and the Chinese Postman Variant

Directed graphs change the question because each edge has a direction. Crossing from A to B doesn't automatically let you travel from B to A along that same edge.

The undirected even-degree rule therefore isn't enough. For a directed graph to have an Euler circuit, every vertex must satisfy:

In-degree equals out-degree.

Every vertex with nonzero degree must belong to one strongly connected component.

In-degree counts arrows entering a vertex. Out-degree counts arrows leaving it. A vertex with three incoming arrows and three outgoing arrows is locally balanced, but local balance alone doesn't guarantee a complete directed circuit. The directed structure must also allow one closed traversal through all edge-bearing vertices.

Suppose one directed cluster has balanced in-degree and out-degree but no directed route reaches a second balanced cluster. The degree counts look correct at every vertex, yet one circuit can't cover both clusters. Strong connectivity supplies the missing global condition.

The distinction resembles a finite-state machine, where permitted transitions depend on direction and state. This example of a finite-state machine can help if directed graphs feel more like labelled transitions than road maps.

The Chinese Postman connection

An Euler circuit requires every edge to be covered exactly once. The Chinese Postman problem relaxes that requirement: find the shortest closed walk that covers every edge at least once. If the graph already has an Euler circuit, the ideal route needs no repeated edge. If not, a postman-style solution may repeat selected edges to repair the imbalance.

That contrast is useful. Euler circuits represent a perfectly balanced network. Chinese Postman routing handles networks where a practical service route still has to cover everything, even when repeating some connections is unavoidable.

Practice Problems and Solving Tips

Try the diagnostic before looking at the solution sketch.

Problem one

A connected graph has four vertices with degrees 2, 4, 2, and 6. Does it have an Euler circuit?

Solution: Yes. Every degree is even, and the graph is connected. Construct the route with Hierholzer's algorithm.

Problem two

A connected graph has vertex degrees 2, 2, 3, and 3. Does it have an Euler circuit?

Solution: No. The two degree-3 vertices are odd, so a closed edge-covering route is impossible. The graph may support an Euler path with different start and end vertices, but it isn't an Euler-circuit graph.

Problem three

A directed graph has balanced in-degree and out-degree at every vertex, but its nonzero-degree vertices split into separate directed components. Does it have a directed Euler circuit?

Solution: No. Degree equality is necessary, but the edge-bearing portion must also be strongly connected. Without that global reachability, one closed traversal can't cover every directed edge.

Use this compact checklist during an exam:

Count first: Write each vertex degree beside the diagram.

Check connection: Make sure every edge-bearing region belongs to one connected structure.

Separate terms: Ask whether the route is open or closed, and whether it uses every edge.

Construct methodically: Use Hierholzer instead of relying on visual guesswork.

Watch odd vertices: Any odd-degree vertex rules out an undirected Euler circuit.

For directed graphs, replace the even-degree question with the balance test, then verify strong connectivity. If you're studying graph theory alongside diplomacy or international relations, Model Diplomat offers sourced learning materials and structured practice that can help you turn definitions into repeatable problem-solving habits.

Real-World Applications and Where to Go Next

Euler circuits model tasks where a worker must cover every connection once and return to the starting point. Examples include planning garbage-collection routes, checking postal networks, testing circuit-board paths, assembling overlapping DNA fragments, and designing network probes for cybersecurity.

The idea also marks the boundary between easy feasibility tests and harder optimization problems. Study Euler paths when exactly two vertices have odd degree, the Chinese Postman problem when repeated edges are allowed but route length matters, and Hamiltonian circuits when the requirement shifts from covering every edge to visiting every vertex.

A compact recap:

An Euler circuit is a closed trail using every edge exactly once.

In a connected undirected graph, every vertex must have even degree.

Hierholzer's algorithm constructs the route by forming and splicing closed circuits.

Directed graphs require equal in-degree and out-degree plus strong connectivity.

Practice starts with degree counting, not route guessing.

If you want to connect graph constraints with optimization and decision models, this introduction to linear programming problems is a useful next step.

Model Diplomat helps students research political and diplomatic topics with sourced answers, structured courses, daily challenges, and practice designed for Model United Nations and international-relations study. Visit Model Diplomat to build a stronger habit of checking definitions, evidence, and connections before you commit to an answer.