Fleury's Theorem

Fleury's Theorem says a connected graph has an Eulerian trail, a path that uses every edge exactly once, if and only if it has at most two odd-degree vertices.

What is Fleury's Theorem?

Fleury's Theorem is the graph theory rule in Combinatorics that tells you when you can trace every edge of a connected graph exactly once without lifting your pencil. That kind of path is called an Eulerian trail. The theorem gives a clean test: the graph must be connected, and it can have no more than two vertices with odd degree.

The degree of a vertex is just the number of edges touching it. Most of the time, degree is what decides whether you can make a one-pass route through the graph. Even-degree vertices are easy to “leave” and “return” to in pairs, but odd-degree vertices create endpoints that cannot be paired up inside the trail. That is why a graph with exactly two odd-degree vertices has a trail, and the trail must start at one odd vertex and end at the other.

If every vertex has even degree, the graph has something even stronger, an Eulerian circuit. That is a closed trail, so you start and finish at the same vertex while still using every edge once. Fleury's Theorem fits right into the paths, cycles, and walks unit because it is really about whether the graph can be covered by one continuous edge-by-edge route.

The connectedness condition matters too. If the graph is split into separate pieces, one trail cannot reach all of the edges. So before you even count odd vertices, you check that the graph is all one piece. That is where terms like connected graph and graph degree show up together.

A common confusion is mixing up “using every vertex” with “using every edge.” Fleury's Theorem is about edges, not vertices. You can have a valid Eulerian trail even if some vertices are visited more than once, as long as each edge is used exactly once and the odd-degree condition is satisfied.

Why Fleury's Theorem matters in COMBINATORICS

Fleury's Theorem gives you a fast way to decide whether an edge-by-edge route exists before you start hunting for one. In Combinatorics, that saves time on graph problems because you can test the structure first instead of guessing a path and checking it afterward.

It also connects a local feature of a graph, vertex degree, to a global question about traversability. That is a big pattern in graph theory: small counts at each vertex can control whether the whole network can be covered neatly. Once you see that, problems about routes, circuits, and network traversal get much easier to organize.

This theorem shows up whenever a graph is used as a model of streets, drawing paths, or line segments in a puzzle. If a question asks whether you can trace a design without retracing any edge, the first move is to count odd-degree vertices and check connectedness. If there are exactly two, you know the trail has to begin and end there. If there are none, you are looking for an Eulerian circuit instead.

How Fleury's Theorem connects across the course

Eulerian Circuit

An Eulerian circuit is the closed version of the same idea. Fleury's Theorem tells you that if every vertex has even degree and the graph is connected, you can trace every edge once and return to where you started. If the graph has exactly two odd-degree vertices, you do not get a circuit, only an open Eulerian trail.

Graph Degree

Degree is the feature you count first when applying Fleury's Theorem. The number of odd-degree vertices determines whether a trail is possible at all, and which vertices can be endpoints. So if you miscount degrees, the whole answer breaks, even if your drawing of the graph looks right.

Connected Graph

Connectedness is the other required condition. Even if the degree counts look perfect, a graph with separate components cannot have one trail that uses every edge. In problem sets, this is the quick check that tells you whether it is worth counting odd vertices in the first place.

breadth-first search

Breadth-first search is not the theorem itself, but it can help you verify that a graph is connected. If a traversal from one vertex cannot reach all others, then Fleury's Theorem does not apply because the graph is disconnected. It is a useful support tool when the graph is messy.

Is Fleury's Theorem on the COMBINATORICS exam?

A problem set question will usually give you a graph and ask whether an Eulerian trail or circuit exists. Your job is to count the degree of each vertex, identify the odd-degree ones, and check whether the graph is connected. If there are exactly two odd vertices, state that the trail starts and ends there. If there are none, name the Eulerian circuit case.

If the question asks you to actually find a trail, you can use Fleury's idea by avoiding bridges until you have to use them. The main skill is not memorizing a long proof, but reading the graph structure correctly and explaining why the trail is or is not possible.

Fleury's Theorem vs Eulerian Circuit

These are closely related, but not the same thing. Fleury's Theorem is the condition for when a connected graph has an Eulerian trail, while an Eulerian circuit is the special case where the trail starts and ends at the same vertex. The degree rule changes from “at most two odd vertices” to “all vertices even.”

Key things to remember about Fleury's Theorem

• Fleury's Theorem tells you when a connected graph can be traced in one continuous path that uses every edge exactly once.

• A graph has an Eulerian trail if and only if it has at most two odd-degree vertices.

• If there are exactly two odd-degree vertices, they must be the start and end of the trail.

• If every vertex has even degree, the graph has an Eulerian circuit, which is a closed trail.

• The first check is connectedness, because a disconnected graph cannot be covered by one trail.

Frequently asked questions about Fleury's Theorem

What is Fleury's Theorem in Combinatorics?

Fleury's Theorem is the rule that tells you when a connected graph has an Eulerian trail, meaning a path that uses every edge exactly once. The graph can have no more than two odd-degree vertices. If it has two, they are the trail's endpoints.

How do you know if a graph has an Eulerian trail?

First check that the graph is connected. Then count the odd-degree vertices. If there are 0 or 2 odd vertices, an Eulerian trail exists, and if there are 0, you actually have an Eulerian circuit.

What is the difference between an Eulerian trail and an Eulerian circuit?

An Eulerian trail uses every edge exactly once, but it does not have to end where it started. An Eulerian circuit is the closed version, so it starts and ends at the same vertex. In Fleury's Theorem, all even degrees give a circuit, while exactly two odd degrees give only a trail.

How do you use Fleury's Theorem on a graph problem?

Count the degree of each vertex, find the odd ones, and check whether the graph is connected. If the graph passes the theorem, you can either identify the endpoints of the trail or use Fleury's algorithm to build one by avoiding bridges when possible.