Copyright

Euler Paths and Euler's Circuits

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Mathematical Models of Euler's Circuits & Euler's Paths

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:01 An Euler Path
  • 1:43 Example 1
  • 3:10 An Euler Circuit
  • 4:33 Example 2
  • 5:09 Lesson Summary
Add to Add to Add to

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Login or Sign up

Timeline
Autoplay
Autoplay
Speed

Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Yuanxin (Amy) Yang Alcocer

Amy has a master's degree in secondary education and has taught math at a public charter high school.

Watch this video lesson, and you will see how you can turn a math problem into a challenging brain game. Learn what it means for a graph to be Eulerian or semi-Eulerian.

An Euler Path

I remember being challenged to a brain game where I am given a picture of a graph with dots and connecting lines and told to figure out a way to draw the same figure without lifting my pencil and only drawing each side once. I was not allowed to go over a side I had already drawn. Little did I know then that what I was doing was actually related to the topic we are discussing in this video lesson.

What I did was I drew an Euler path, a path in a graph where each side is traversed exactly once. A graph with an Euler path in it is called semi-Eulerian. I thoroughly enjoyed the challenge and thought little of the math connections it had. Let me show you the brain game I was given.

Eulerian

To draw this shape without lifting my pencil and going over each line exactly once, I had to begin at the point 1, then go to point 3, then 2, then 4, and then 3 again. Do you see how we went over each line just once? That is the defining characteristic of an Euler graph. Also, note that we ended up in a different spot.

Another characteristic of a semi-Eulerian graph is that at most two of the vertices will be of odd degree, meaning they will have an odd number of edges connecting it to other vertices. All the other vertices will be even. In this graph, we see that vertices 1 and 3 are odd, while 2 and 4 are even.

Example 1

Let's look at another example. This time, see if you can figure it out.

Eulerian

Again, what we are trying to do is to find a path in the graph so that we are crossing every edge exactly once. Remember that a path takes you from one point to a different point. Can you find one in this graph?

Try starting at point 2. Now go down to point 1. Then point 4, back to point 2, point 3, and then finally point 4. We have an Euler path! We have crossed each edge exactly once. So this means that this graph is semi-Eulerian.

Are there other Euler paths in this graph? Yes, there are. We can also note these Euler paths by just writing the names of the vertices that we pass. So, another Euler path in this graph is 4, 3, 2, 4, 1, 2. Notice that with all these paths, we end up at a different point than where we began. Are there more ways to draw this shape using an Euler path? I won't tell you what they are, but I will tell you there are a total of 6 Euler paths in this graph. What makes each path different is the order in which the edges are drawn.

An Euler Circuit

If we end up at the same point that we started, then we have what is called an Euler circuit, a circuit in a graph where each edge is traversed exactly once and that starts and ends at the same point. Look at this graph and see if you can draw it without lifting your pencil, going over each edge only once, and starting and ending at the same point:

Eulerian

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support