Copyright

Eulerizing Graphs in Math

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Hamilton Circuits and Hamilton 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:02 A Graph
  • 1:01 Fleury's Algorithm
  • 1:49 Eulerizing a Graph
  • 3:20 Semi-Eulerizing a Graph
  • 5:05 Lesson Summary
Save Save Save

Want to watch this again later?

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

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed
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.

After watching this video lesson, you will be able to Eulerize any graph. Learn what it takes to create a Eulerian graph from a non-Eulerian graph. Learn what Fleury's algorithm has to do with all of this.

A Graph

We begin with a graph - this graph:

Eulerizing

Now, imagine that you are a chief engineer for the town of Harrisville. Your job is to create roads that will make it easy to navigate the town for both residents and workers, especially the mailman. You want to build the roads in such a way so that the mailman can have an optimized route where he passes each road only once.

In order to do this, you make use of your knowledge of graph theory. Why? Because this graph that you are looking at is actually a drawing of the current roads of the town. The intersections are marked with the dots with numbers in them. You know that when a graph has an Euler circuit or Euler path, then that means the graph is mailman-friendly because there is a route that he can take to pass each road just once. The only difference being that the path takes the mailman to a different end point, and the circuit has the mailman ending where he began.

Fleury's Algorithm

You also make use of Fleury's algorithm that tells you that when a graph has zero odd vertices, then it has an Euler circuit, and when the graph has two odd vertices, then it has an Euler path. Knowing this helps you to analyze your current graph to see if the roads are already mailman-friendly. You count the number of odd vertices; remember that an odd vertex is a vertex where the number of edges connecting it to other vertices is odd. In your graph, you count four odd vertices. Hmmm. This means that there currently is no Euler path or Euler circuit in this graph. What are you to do?

Since you are the chief engineer for this town, you go ahead and propose some new roads. But where should you place these roads? Which intersections should the new roads connect?

Eulerizing a Graph

The purpose of the proposed new roads is to make the town mailman-friendly. In graph theory terms, we want to change the graph so it contains an Euler circuit. This is also referred to as Eulerizing a graph. The most mailman-friendly graph is the one with an Euler circuit since it takes the mailman back to the starting point. This means that the mailman can leave his car at one intersection, walk the route hitting all the streets just once, and end up where he began. There is no backtracking or walking of streets twice. This saves him time.

We used Fleury's algorithm to help us determine whether our graph has an Euler circuit to begin with. We can also use Fleury's algorithm to help us decide where to place our new roads, our new edges. According to Fleury's algorithm, in order for a graph to have an Euler circuit, all of the vertices must be even, meaning we have zero odd vertices. To accomplish this, we can draw new lines connecting vertices that are odd together to make them even.

For example, we can connect vertices 3 and 2 together. This changes these two vertices from odd to even. Now we are left with two odd vertices, vertices 4 and 5. To change these to even vertices, we can add another road connecting these two. This changes our graph to one where there are zero odd vertices, meaning that we have a graph with an Euler circuit in it. We have Eulerized our graph by adding two new roads.

Eulerizing

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 200 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