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 understand how Euler's circuit theorem, Euler's path theorem, and Euler's sum of degrees theorem will help you analyze graphs. Also, get some practice with the quiz.
In this video lesson, we will go over three of Euler's theorems relating to graph theory. Why are these important? These are important because they help you to analyze graphs such as this one:
Why are graphs such as these important? If our graph represents a neighborhood where the dots are intersections and the lines are the roads, then graph theory can help us find the best way to get around town. For example, graph theory can help the mailman deliver his mail so that he doesn't have to back-track or pass by the same road twice. Euler's theorems come in handy because they tell the mailman whether an efficient route is even possible just from looking at the graph. How does this work? Let's take a look at Euler's theorems and we'll see.
Euler's Circuit Theorem
The first theorem we will look at is called Euler's circuit theorem. This theorem states the following: 'If a graph's vertices all are even, then the graph has an Euler circuit. Otherwise, it does not have an Euler circuit.' What does this mean for our mailman?
Recall that an Euler circuit is a route where you can pass by each edge or line in the graph exactly once and end up where you began. This helps the mailman figure out whether there is a route that he can take where he ends up where he began and where he goes through each road just once. If such a route doesn't exist in the first place, then there is no point for him to even try to figure one out. Our vertices are of even degree if there is an even number of edges connecting it to other vertices.
If all vertices have an even degree, the graph has an Euler circuit
Looking at our graph, we see that all of our vertices are of an even degree. The bottom vertex has a degree of 2. All the others have a degree of 4. This means that the graph does have an Euler circuit. This tells the mailman that, yes, there does exist a route where he doesn't have to back-track. He can now go about figuring out such a route.
Euler's Path Theorem
This next theorem is very similar. Euler's path theorem states the following: 'If a graph has exactly two vertices of odd degree, then it has an Euler path that starts and ends on the odd-degree vertices. Otherwise, it does not have an Euler path.'
Recall that an Euler path is a path where you pass by each edge or line in the graph exactly once, and you end up in a different spot than where you began. A path is very similar to a circuit, with the only difference being that you end up somewhere else instead of where you began. An Euler path is good for a traveling salesman or someone else who doesn't need to end up where he began. Looking at our graph, we see that we don't have any vertices that are odd. This tells us that this graph does not have an Euler path in it.
Over 79,000 lessons in all major subjects
Get access risk-free for 30 days,
just create an account.
This next theorem is a general one that works for all graphs. Euler's sum of degrees theorem tells us that 'the sum of the degrees of the vertices in any graph is equal to twice the number of edges.' This means that if we have 3 edges, then we will get 6 after adding up the degrees of each vertex. Let's look at our graph and see if this theorem is true. We expect the total number of degrees from our vertices to add up to twice the number of edges in our graph. Let's see how.
First, let's count the edges. We have 11 edges. This means that we should expect the total number of degrees to add up to 22. Let's see if it does. The bottom vertex has a degree of 2. The rest have a degree of 4. So, we have 2 + 4 + 4 + 4 + 4 + 4 = 22. Hey, look at that; we got 22! Just like the theorem says! It works. Why is this theorem useful? This theorem lets you know whether or not the graph you are looking at is legit.
Let's review what we've learned. We learned that Euler's circuit theorem states this: 'If a graph's vertices are all even, then the graph has an Euler circuit. Otherwise, it does not have an Euler circuit.' Euler's path theorem states this: 'If a graph has exactly two vertices of odd degree, then it has an Euler path that starts and ends on the odd-degree vertices. Otherwise, it does not have an Euler path.' Euler's sum of degrees theorem tells us that 'the sum of the degrees of the vertices in any graph is equal to twice the number of edges.'
These theorems are useful in analyzing graphs in graph theory. Euler's circuit and path theorems tell us whether it is worth looking for an efficient route that takes us past all of the edges in a graph. This is helpful for mailmen and others who need to find a most efficient route.
Once you are finished with this lesson you should be able to:
State three of Euler's theorems
Determine if a graph has an Euler's circuit
Define a Euler's path
Recall why Euler's theorems could be useful in real life
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.