Euler Paths and Circuits | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Euler Paths and Circuits

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

← Graph Isomorphism and HomomorphismNext lesson: Fleury's Algorithm →

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

Crossing every edge exactly once - decided by counting odd degrees.

  • Define Euler paths and Euler circuits
  • State the degree condition for each
  • Apply it to Königsberg and a network
  • Explain why connectivity is a separate requirement

Transcript

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

Graph Theory: Foundations and Euler Paths

Euler Paths and Circuits

This section asks when it's possible to travel through a graph, crossing every edge exactly once. The answer turns out to depend on nothing more than counting the vertices of odd degree. It's one of the oldest results in graph theory, and one of the most useful.

The Opening Problem

Cross Every Cable Exactly Once

Return to the data center from section nine point three. The leaf switches, spine switches, and redundant cabling are all in place. Before the system goes live, an engineer wants to run a diagnostic packet that walks the physical topology, crossing every cable exactly once, to confirm each link carries traffic. Two questions matter. First, can such a walk be built at all for this wiring? Or does the topology make it impossible, however cleverly it's routed? Second, if it's possible, must the walk return to its starting switch, or can it end somewhere else? Both have a satisfyingly short answer. It depends entirely on how many switches have an odd number of cables attached. Nothing more exotic than a count of degrees.

Definitions 9.5.1 and 9.5.2

Trails That Use Every Edge

Recall from section nine point two. A trail is a walk with no repeated edge, and a circuit is a trail that ends where it started. An Euler path, also called an Euler trail, is a trail that includes every edge of the graph exactly once. Its start and end can differ. An Euler circuit is an Euler path that also closes up, starting and ending at the same vertex. Two points are easy to misread. An Euler path may repeat vertices. A switch visited twice is fine, as long as no cable is crossed twice. And every edge means the entire edge set. A trail using eleven of twelve edges is not an Euler path, however much of the graph it covers.

Theorem 9.5.1

The Degree Condition

Whether a graph has an Euler circuit, an Euler path, or neither, is fully determined by one structural feature. The number of vertices with odd degree. Take a connected graph with at least one edge. Isolated vertices with no edges don't count against connectivity here. If every vertex has even degree, meaning zero odd vertices, the graph has an Euler circuit. If exactly two vertices have odd degree, it has an Euler path that isn't a circuit. And every such path must start at one of those two vertices, and end at the other. With any other number of odd vertices, four, six, and so on, it has neither. This section uses the theorem as a tool. The proof, including how to actually build the circuit, comes in section nine point seven.

Why It's So Useful

A Search Replaced by a Count

The practical value is huge. Instead of an exhausting search, trying different edge orderings to see if one works, you make a single pass over the degrees. Those can be read straight from an adjacency list or matrix, in time proportional to the number of edges. And notice that the count of odd vertices is never one, or three. By the handshake lemma from section nine point two, the number of odd-degree vertices is always even. So two is the smallest nonzero count possible. That's why exactly two is the meaningful dividing line between a circuit and a path.

Example 9.5.1

The Seven Bridges of Königsberg, 1736

The historical origin is Leonhard Euler's analysis of the city of Königsberg, in seventeen thirty-six. The city had four landmasses, two of them islands in the river, joined by seven bridges. Residents wondered whether a walk could cross each bridge exactly once, and return to its start. Model each landmass as a vertex and each bridge as an edge. That gives a multigraph on four vertices, with degrees five, three, three, and three. All four vertices have odd degree. That's not zero, and not exactly two. So there's neither an Euler circuit nor an Euler path. No such route can exist, wherever it starts. Euler reached that by exactly this degree-counting argument, without trying routes. It's generally credited as the founding result of graph theory.

Example 9.5.2

The Data-Center Walk

Now the diagnostic walk. Suppose the topology has five switches, P, Q, R, S, and T. The cables form a ring, P Q, Q R, R S, S T, and T P, plus one more, from P to R. P has degree three, Q two, R three, S two, and T two. They add to twelve, twice the six cables, so the handshake lemma checks out. Exactly two vertices, P and R, have odd degree. So there's an Euler path, a walk crossing every cable exactly once, but no Euler circuit. And any such walk must start at P and end at R, or the reverse. One is P to Q, Q to R, R to S, S to T, T to P, and finally P to R.

Figure 9.5.1

A Circuit and a Path, Traced

This picture traces both cases. On the left, a plain four-cycle. Every vertex has degree two, which is even. So the numbered walk, one through four, is an Euler circuit, closing back at W. On the right, the data center graph. P and R, the two odd-degree vertices, are highlighted. The numbered walk, one through six, is an Euler path from P to R. And if the diagnostic tool needed the walk to return to its start, the fix is clear. Add a second cable between P and R. Both reach degree four, every degree is even, and an Euler circuit appears.

Re-Check After Every Change

1 Edge Changes the Answer

The degree condition has to be rechecked after any change to a graph. The four-cycle has every degree two, so it has a circuit. Add one diagonal, from W to Y. Now W and Y have degree three, two odd vertices. There's still an Euler path, but no longer a circuit. Add the other diagonal too, from X to Z. Now every vertex has degree three. Four odd vertices, so neither exists. So the theorem doesn't only say whether a walk exists. The odd vertices it identifies are exactly the points to modify.

Table 9.5.1

3 Outcomes

This table collects the three outcomes. Zero odd vertices gives an Euler circuit. It starts and ends at the same vertex, and any vertex can be the start. The four-cycle is an example. Exactly two odd vertices gives an Euler path, not a circuit. It must run from one odd vertex to the other, like the data center walk from P to R. Any other count, four, six, or more, gives neither. Königsberg is the classic case. The difference between exactly two, and any other even number, is easy to blur when working quickly.

Takeaways

Count the Odd Vertices

To summarize. An Euler path uses every edge exactly once, and vertices may repeat. An Euler circuit is an Euler path that starts and ends at the same vertex. A connected graph has an Euler circuit if it has zero odd vertices, an Euler path if it has exactly two, and neither otherwise. With two odd vertices, they're forced to be the endpoints. Here's something to think about. On a lab bench, there's a ring of six switches, every degree two. Beside it, separately, are two switches joined by a single cable. Each piece, on its own, satisfies a degree pattern that works. But no cable joins the two pieces. As one combined graph, does it have an Euler circuit, an Euler path, or neither? And why is connectivity a separate, non-negotiable requirement, not something the degree condition already guarantees?

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 Euler Paths and Circuits

What is the difference between an Euler path and an Euler circuit?
An Euler path is a trail that uses every edge of a graph exactly once, and it may start and end at different vertices. An Euler circuit is an Euler path that starts and ends at the same vertex. Both may repeat vertices, but neither may repeat an edge or skip one.
How do you tell from vertex degrees whether a graph has an Euler path or circuit?
Count the vertices of odd degree in a connected graph. Zero odd vertices means an Euler circuit exists. Exactly two odd vertices means an Euler path exists but no circuit, and it must run from one odd vertex to the other. Any other count, such as four or six, means neither exists.
Why is there no Euler path across the seven bridges of Königsberg?
The Königsberg graph has four odd-degree vertices, so it has neither an Euler circuit nor an Euler path. Modeling each landmass as a vertex and each bridge as an edge gives degrees 5, 3, 3, and 3. Since the count of odd vertices is neither 0 nor 2, no route can cross every bridge exactly once.
Why does an Euler circuit require a connected graph if all degrees are even?
Even degrees alone do not suffice, because a single walk cannot reach pieces that no edge links. Take a six-vertex ring and a separate triangle: every vertex has degree 2, yet no trail covers both. Connectivity must be checked separately, apart from isolated vertices that have no edges.

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 →