Determine If a Graph Has an Euler Circuit

(male narrator) So suppose we got a graph here, and we're wondering does this graph have an Euler path? Have an Euler circuit? Well, it turns out that there's a really easy way to tell, and it comes down to the degree of the vertices. Uh...and so... it turns out that in order to have an Euler circuit, all vertices... all vertices must have... must have even degree. Even being like 2, 4, 6, 8. Right? Even-numbered degrees. And the idea is really simple. That the idea is we need to make it so that every time we come into a vertex, we have a way out. So if I have another way in, I need another way out. And so we need even degrees, uh...on all of our vertices. For an Euler path, it's similar, except we can have up to... we can have, uh...either 0 or 2 odd degree...vertices. Otherwise, all the rest... must be even degree, for the same reason. Now the reason it's okay to have two odd degree vertices is because with an Euler path, we don't have to get back to our starting point. So here, notice that this vertex has Degree 2. This vertex has Degree 3. This one has Degree 1, 2, 3, 4. This one has Degree 1, and this one has Degree 4. And so we have one pair of vertices. Uh...so two vertices with odd degree, and that'll be okay. What it means is that our Euler path is gonna have to start and end at those vertices. So let's see if we can come up with an Euler path here. So I could come down here. I could come up here, over here, up here, uh...uh...down here, back up here, and down there. And there we go. There's my Euler path, starting here and ending at that vertex. Right? Notice there would be no way to do an Euler circuit here. So let's take a look at another one. Does this graph have an Euler path? How about an Euler circuit? Well, let's see, how many odd degree vertices are there? 1, 2, 3...1, 2, 3... 1, 2, 3...1, 2...ah-oh. So in this graph, we have a ton of vertices with odd degree. And so it...there... it's not gonna be possible to come up with a Euler path or an Euler circuit on this graph as drawn. Now that's for this particular problem, which was, uh...you know, for our lawn inspector who was walking along these paths. Now if on the other hand, uh...let's say it's snowing, and we got a snowplow that has to go down every street, but the street is wide enough that it has to drive down twice, then our graph would look more like this, where each edge is gonna be driven over twice. Now if we look at this graph, you can see that every vertex is even degree, and so this graph will indeed have an Euler circuit, uh...because, uh...every vertex has even degree. So the snowplow would have a route where it could drive over every street twice. Right? Once in one direction, and once in the other direction. Uh...it could drive over every street twice, uh...and get back to the starting point.