[MUSIC]

And so now we can ask the same question we asked before, is there

an algorithm that determines, given a graph, whether it's Eulerian or not?

And that brute force approach that we talked about before would still

work, right.

We could still generate all sequences of vertices, check whether they're paths and

check whether they're Eulerian.

And that's fine, but we talked about how it wasn't efficient.

And in fact for Eulerian graphs, there's an easier way.

And so, if we think back to our two examples of Eulerian graphs from those

just toy, basic examples, we can think about how we may have

come up with the Eulerian paths that visit every edge exactly once in these graphs.

And notice that when we were thinking about these Eulerian paths,

It was important which vertex we started with.

So for example, in the one graph,

we can't start at one of the side vertices.

We have to start in one of the two middle vertices,

because if we try to start on one of the sides, then we're gonna get stuck and

not be able to come to visit every edge.

And the algorithm is based on the observation That

when we have an Eulerian path we have to have each edge traverse exactly once and

so we can think about these edges as taking us to and from vertices.

And so what we're doing is we're partitioning all of the edges in the graph

and based on the sequence of edges that we traverse in the path and some of these

edges bring us into vertices and some of these edges take us out of vertices.

And so if we're focused on any one vertex,

in order to have an Eulerian path we have to have the same number of edges

going into that vertex as are going out of that vertex.

And so what that means is that most of the vertices in the graph need to be of

even degree in order for there to be an Eulerian path through this graph.

And We might be able to accommodate two exceptions.

Our starting vertex is allowed to have more outgoing edges than incoming edges,

and our ending vertex is allowed to have more incoming edges than outgoing edges.

And so the criterion for being is that there's, at most,

two vertices of odd degree in the graph.

And it turns out that If we have at most 2 vertices of odd degree,

then we can come up with algorithmically an Eulerian path through this graph.

Just starting at one of those odd degree vertices and

figuring out how to go from there.

And ditto If we know that our graph is Eulerian we can guarantee that it has

at most two vertices of odd degree, and so it's a really cool theoretical theorem

that you can prove about this equivalence between this notion of Eulerian and

the degree structure of the graph, and, well who cares?

One reason is that it gives us a much faster algorithm for

determining whether a graph is Eulerian but again who cares.

And the reason we care is that, A, we see the small changes in

the definition lead to really big algorithmic differences, and, B,

what that does is it gives us a direction to go.

If we're trying to use graphs to solve real world problems,

then what we want to do is model our real world problems in ways that lead

themselves to solutions via looking for Eulerian paths or looking for other graph

properties that are efficient to determine or have efficient algorithms for them.