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.