And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. So by the end of this video you'll be able to talk about what it means for a graph to be Hamiltonian and to determine whether, for small examples, that particular graph is Hamiltonian. And we'll think about algorithms for answering this question for bigger and more systematic graphs, and we'll talk about the efficiency of that algorithm. So let's jump in, so we were talking about the traveling salesperson problem where our graph really represents cities and we've got N cities, one of which is our designated hometown and we know all of the pairwise distances between the cities. And what we like to do is find a tour that starts at hometown goes around all of these cities and comes back home. Now, we know that this is possible, we've talked a little bit about algorithms for travelling sales person but what if we change it a little bit. So for example, if now we don't care about distance so much. But we just wanna go from one vertex, all through, all the vertices in the graph and make sure we arrive at each vertex exactly once. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. The question how, becomes, though, what if some edges are missing? Many of the graphs that we're thinking about, we don't have a complete graph. We don't have edges between every two vertices, and so we could ask the question is there a path through the graph that visits every vertex exactly once when our graph is a general graph? May or may not be complete. Now we're just going to focus on undirected graphs so we're not worried about the directions of the edges. So let's think about some examples and how this works. And with each one of these, I'd like you to try thinking about whether the graph is Hamiltonian or is not Hamiltonian and then we'll think about it together as well. So a graph is Hamiltonian if there is such a path through the graph which visits each vertex exactly once. Let's look at this particular graph. Is it Hamiltonian? All right, we'll come back. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. What we could do is we could just start at the top, and then come towards the front, and go along the front vertices. Then go back and go down and go back bottom corner, and we've got a path that starts its own vertex and visits every vertex in the graph exactly once, so this graph is Hamiltonian. Now how about this one? Is it Hamiltonian? All right, welcome back. This graph is not Hamiltonian and in order to justify that the graph is not Hamiltonian we have to do something called little bit more new ones than our justification that the graph is Hamiltonian. Cuz, think about what the definitions are saying in order to prove that graph is Hamiltonian we just need to produce this tour or this path that goes along the graph and visits every vertex exactly once. All right, but to prove that a graph is not Hamiltonian we have to say that no such path exists, that no matter how we try to visit each vertex exactly once, we're gonna fail somehow. So, we can make that argument with this graph. If we start in the middle vertex then we're going to have to visit one of the, one of the periphery vertices after that and so maybe we jump up top, but then we're stuck because we can't jump back to the middle because we already visited the middle and Hamiltonian paths aren't allowed to visit vertices more than once. All right, so a Hamiltonian tour can't start in the middle. Now, could it start in the periphery? Well, the problem with starting in a periphery is that the first step of the path will be to have to go to the middle because the periphery vertices just have degree one. They're only adjacent to the middle vertex. Then once we get to the middle we're in the same situation as before because our Hamiltonian path would have to visit both of the periphery vertices but we can't get from one to the other. Other than by going back to the middle, which we can't do in a Hamiltonian path because we've already visited the middle vertex. Okay. This graph is not Hamiltonian. And, so now we've seen an example of a Hamiltonian graph and one that is not. And then the question is how do we decide this in general? And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. How do you decide if those graphs are Hamiltonian? And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And it seems a bit daunting if we have a graph that even has just hundred of vertices, thousands of vertices, millions of vertices, to try all possible paths or to do this reasoning about these graphs. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And then once we've checked that we can say is this sequence of vertices denoting a Hamiltonian path? Does every vertex appear exactly once? And we could do that, we could code off of brute force implementation, just like you've seen before in Christine's brute force implementation of travelling salesperson. But brute force implementations are not efficient, they're gonna take a really long time, so is there a better way than just trying all possible paths? Now, the piece where we verify whether a particular sequence of vertices is a Hamiltonian path, that part was efficient. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And this is exactly what Leo was talking about when he was talking about NP completeness. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. it's a problem where we don't know of an efficient solution which, given a graph, tells us whether there is a Hamiltonian path through that graph or not. But if someone were to produce a candidate Hamiltonian path for us, we would be able to check whether candidate Hamiltonian path is, indeed, a Hamiltonian path. We're stuck with this graph question, which is a very natural graph question, but for which we don't have an efficient solution. So we could say what's next? What do we do? Are any graph problems really this hard? We saw the travelling salesperson was hard. We're seeing now the Hamiltonian paths are hard. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with. And so in the next video, we're gonna tweak this graph problem just a little bit, and see if maybe we can get a slightly easier graph problem to work with.