Fleury's Algorithm | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 9.6 Free with a free account

Fleury's Algorithm

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.6 · lesson 64 of 878 min · free with a free account

← Euler Paths and CircuitsNext lesson: Euler's Theorems: Degrees, Paths, and Circuits →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Building an Euler path edge by edge - without burning bridges.

  • State Fleury's algorithm step by step
  • Define a bridge and apply the bridge rule
  • Trace the algorithm to a complete Euler path
  • Compare it with Hierholzer's algorithm

Transcript

Everything said in the video, section by section (1,210 words). Read along, or search it.

Graph Theory: Foundations and Euler Paths

Fleury's Algorithm

Section nine point five told us when an Euler path or circuit exists. This section shows how to actually build one. Fleury's algorithm constructs the route one edge at a time. Its entire correctness rests on a single rule, often summed up as don't burn your bridges.

The Opening Problem

A Drone Inspecting Power Lines

A municipal utility operates a drone that inspects overhead power lines. To save flight time and battery, it should cross every line segment in a district exactly once, never doubling back over one it's already inspected. Section nine point five settled when that's possible. A connected graph has an Euler circuit when every degree is even, and an Euler path when exactly two degrees are odd. But that answers whether a route exists, not how to build one. An operator who knows a route exists still needs a concrete flight plan. Fleury's algorithm answers that. It's a step-by-step greedy procedure that constructs the route edge by edge. The one subtlety is choosing, at each vertex, which unused edge to take next. The wrong choice can strand the route, with unreachable edges still unused.

Algorithm 9.6.1

Fleury's Algorithm

The algorithm assumes the graph is connected, and already satisfies the criterion from section nine point five. It doesn't recheck that. Step one, choose a start. With two odd-degree vertices, start at either one, and the route will finish at the other. With none, start anywhere, and the route will return. Step two, look at the unused edges at the current vertex. Call the graph of not-yet-used edges H. Step three, choose. If only one unused edge remains, take it. If several remain, don't choose a bridge of H, unless every option is a bridge. Step four, traverse the edge. Mark it used, move to its other end, and remove it from H. Then repeat until every edge is used, and report the route. All the steps except step three are bookkeeping.

Definition 9.6.1

Bridges

So what is a bridge? An edge of a graph is a bridge, or cut-edge, if removing it increases the number of connected components. Equivalently, a bridge lies on no cycle. An edge that isn't a bridge always lies on some cycle, so an alternate route between its ends survives when it's removed. The word currently matters. An edge that isn't a bridge in the original graph can become one later, once enough of the edges around it have been used up. So Fleury's algorithm rechecks bridge status against the remaining graph H, at every single step, not just once at the start.

Lemma 9.6.1

Don't Burn Bridges Unless Necessary

Here's why the rule is necessary. Suppose the edge from u to v is a bridge of H. Removing it splits H, leaving u in one piece and v in another. If unused edges still remain in u's piece, and the algorithm crosses the bridge anyway, the route is now in v's piece. And since the bridge has been used, no remaining edge leads back. The edges left behind can never be reached, and the algorithm can't finish. Choosing a non-bridge instead, whenever one exists, keeps the current piece connected, so every remaining edge stays reachable. That makes the rule a genuine necessity, not a convenient heuristic. A graph with a valid route can still get stuck, because of one earlier greedy choice.

Worked Example 9.6.1

A Fiber-Maintenance Loop

Here's a complete trace. A small fiber-optic maintenance loop has seven junction boxes. A, B, and C form one triangle. D, E, and F form another. And the two triangles are joined only through a path from C, to M, to D. C and D each have degree three. Every other vertex has degree two. So there are exactly two odd-degree vertices. That means an Euler path exists between C and D, but not a circuit. Start at C.

The Trace

Only 2 Real Decisions

At C, all eight edges are unused. The options are C A, B C, and C M. Removing C A leaves A reachable through B, so it isn't a bridge. The same goes for B C. But removing C M cuts the triangle off from everything else. It's a bridge. Two non-bridge options exist, so C M must be avoided. Choose C A. From A, the only unused edge is A B. From B, the only one is B C. Both are forced. Back at C, only C M remains. It's a bridge, but it's the only option. That's the unless necessary clause. Cross it, then M D, which is forced too. At D, two options remain, D E and F D. Neither is a bridge in the remaining triangle, so either is valid. Choose D E. Then E F and F D are forced, ending at D. Only two steps involved a real decision. Every other step was forced.

Figure 1

The Route, Edge by Edge

Here's the whole route, with edges numbered in the order they're used. The two red edges, C to M and M to D, are the only links between the triangles. They're bridges from the very start. The route is C, A, B, C, M, D, E, F, D. It finishes the left triangle before committing to the one-way crossing. And it ends at D, the other odd-degree vertex, exactly as section nine point five predicts.

Listing 1

The Bridge Rule in Code

The code mirrors the trace directly. While edges remain, it looks at the current vertex's neighbors, in sorted order for a deterministic tie-break. If there's only one, the move is forced. Otherwise, it keeps only the choices that aren't bridges, and takes the first. It uses a bridge only when forced. The bridge test temporarily removes the edge, checks with a breadth-first search whether its two ends can still reach each other, and then restores it. Running it on the fiber graph prints C, A, B, C, M, D, E, F, D. It reproduces the hand trace exactly.

Table 2

Fleury Versus Hierholzer

Fleury's algorithm isn't the only way. Hierholzer's algorithm solves the same problem differently. Fleury extends a single route greedily, checking bridge status at each choice. Hierholzer builds small closed circuits, and then splices them together into one. Fleury needs a reachability search at every vertex with a choice. So a straightforward implementation takes time roughly proportional to the number of edges squared. Hierholzer needs no bridge checks, and runs in time roughly proportional to the number of edges. Fleury's strength is transparency. Its logic is easy to trace by hand. Hierholzer is faster, and it's what graph software typically uses on large graphs.

Takeaways

Anchor the Route, Then Cross

To summarize. Fleury's algorithm builds an explicit Euler path or circuit, one edge at a time, for a graph that already meets the degree criterion. When there's a choice, it never crosses a bridge of the remaining graph, unless every option is a bridge. Bridge status is rechecked at every step, since edges can become bridges as the route uses up their neighbors. And crossing a bridge too early can strand edges, even though a valid route exists. Here's something to think about. At the very first step, the trace chose C A. Suppose it had chosen B C instead. Would the path change, and how? More importantly, does Fleury's algorithm ever guarantee a unique Euler path? Or only that some valid path will be found? What does that say about calling its output the Euler path, rather than an Euler path? And why does step three only ever rule out bridges, and never choose between non-bridges?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Fleury's Algorithm

What is Fleury's algorithm for finding an Euler path or circuit?
Fleury's algorithm is a greedy procedure that builds an Euler path or circuit one edge at a time in a connected graph that already meets the degree criterion. Start at an odd vertex if there are two, otherwise anywhere. At each step, take an unused edge, avoiding bridges of the unused graph unless no other option exists. Mark the edge used and repeat.
What is a bridge in a graph, and what is the bridge rule?
A bridge, or cut-edge, is an edge whose removal increases the number of connected components, so it lies on no cycle. The bridge rule says that when several unused edges leave the current vertex, do not pick a bridge of the remaining graph H unless every option is a bridge. Crossing one too early can strand unused edges behind it.
How do you trace Fleury's algorithm on a graph with two triangles joined by a path?
Take triangles A,B,C and D,E,F joined by the path C–M–D. Only C and D have odd degree, so start at C. Avoid the bridge CM and go C,A,B,C, then cross M to D, and finish D,E,F,D. The full route is C,A,B,C,M,D,E,F,D, ending at the other odd vertex.
How does Fleury's algorithm differ from Hierholzer's algorithm?
Fleury's algorithm extends one route greedily and checks bridge status at each choice, while Hierholzer's algorithm builds small closed circuits and splices them together. Because Fleury needs a reachability search at each choice, a straightforward implementation takes time roughly proportional to E^2. Hierholzer needs no bridge checks and runs in roughly E time, so software typically prefers it for large graphs.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →