Hamiltonian Cycles, Graphs, and Paths | Hamilton Cycles, Graph Theory

what our Hamiltonian cycles in graph theory that's what we'll be going over in today's wrath of math lesson we'll also talk about Hamiltonian paths and Hamiltonian graphs you might already be familiar with a similar concept of an Euler circuit which is a circuit that contains every edge of a graph a similar question you might ask is if a graph has a cycle that contains every vertex of the graph such a cycle is called a Hamiltonian cycle that's what we'll be talking about today and we'll begin by looking at a graph and an example of a Hamiltonian cycle so here's a beautiful graph I've labeled its vertices A through D so does this graph have a Hamiltonian cycle a cycle that contains every vertex indeed it does and you might be able to see one yourself let me draw on one we could start at the vertex a and then go to the vertex C then to the vertex D then to B and then back to a where we started this is a Hamiltonian cycle a cycle that contains every vertex of the graph when we're talking about simple graphs cycles are most easily defined as sequences of vertices where consecutive vertices are adjacent and no vertices are repeated except for the first and the last which are equal so let's write out this Hamiltonian cycle as a sequence of vertices we start at a then we go to C then we go to D then we go to B and then we return to a where we started so that is an example of a cycle now for a cycle like this to be Hamiltonian the sequence has to contain every vertex of the graph in this case of course it does a a c c DD b and then we go back to a we've got every vertex of the graph in that Hamiltonian cycle if a graph has a Hamiltonian cycle you might be able to guess we call it a Hamiltonian graph or simply a Hamilton graph so this is a Hamiltonian graph if you want to prove the graph is Hamiltonian you got to prove that it has a Hamilton cycle a cycle like this that contains every vertex of the graph something interesting you might notice about a Hamiltonian cycle is that if we delete an edge from the cycle we're left with a neat sort of path let's say we delete this edge here now we've got a path going from D all the way to C let's write that out also as a sequence of vertices we go from D to B to a to C this is a path that contains every vertex of this graph such a path as you might be able to guess is called a Hamiltonian path so this is a Hamiltonian path whenever we have a Hamiltonian cycle we can create a Hamiltonian path by deleting one edge from the cycle the converse is not necessarily true if we have a Hamiltonian path we may or may not be able to find a Hamiltonian cycle in that graph here's a very simple example any path graph will do let's look at the path graph on four vertices this path graph clearly has a Hamiltonian path we could go from if we label these vertices go from vertex one to two to three to four and that's a path in the graph that contains every vertex however there's no Hamiltonian cycle in that graph once we get to vertex four there's no way that we're going to get back to where we started without passing through vertices and edges multiple times which isn't allowed so if we have a Hamiltonian path we may or may not be able to get a Hamiltonian cycle in that graph but if we have a Hamiltonian cycle we can delete any one edge and end up with a Hamiltonian path now we mentioned Euler circuits earlier and there is a very nice necessary and sufficient condition to know if a graph has an Euler circuit a graph has an Euler circuit and only if every vertex in the graph has an even degree there's no super handy condition like that for hamiltonian graphs but of course we can talk about some necessary conditions and we could talk about some sufficient conditions we'll talk about some necessary conditions for a graph to be hamiltonian in this lesson so these are conditions that if a graph doesn't meet them then it's not Hamiltonian if a graph does meet them it might be Hamiltonian but we don't know so let's talk about some one very obvious necessary condition for a graph to be Hamiltonian is that it has to be connected if a graph is disconnected there's no way it's going to contain a cycle that contains every vertex of the graph because there's going to be some vertices in another component that you can't get to another less obvious condition for a graph to be Hamiltonian is that it cannot have any cover disease remember that a cut vertex is a vertex that when deleted disconnects its graph so to see why it's necessary that a graph has no cut vertices in order for it to have any chance of being Hamiltonian let's come over here and draw a quick diagram so suppose we have a graph that has a cut vertex then we can draw it kind of like this there's some piece of the graph over here and there's some piece over here and they're connected only by this cut vertex there might even be you know multiple edges going to that cut vertex but if you delete that vertex cuts the graph leaving two components behind a graph like this certainly cannot be Hamiltonian because at some point you're going to have to pass through this cut vertex to get to one piece of the graph and then you're not going to be able to get back to where you started without passing through that vertex again if you start in this piece you're gonna have to pass through the cut vertex to get here and then you'd have to pass through it again to get back and that's not allowed if you start at the cut vertex and go to either one the pieces you're going to have a similar problem so it's another necessary condition a graph needs to have no cut vertices to have any chance of being Hamiltonian let's mention one other condition for a graph to be hamiltonian one other necessary condition and actually before I write out this condition let's see it in action in this graph here let me erase those blue lines and then I'm going to erase this edge that joins a and C now what I've just done by erasing that edge is I've reduced the degree of a from two to one so here's a problem in a cycle every vertex has to have degree two you got to have one edge going to the vertex I say going you know informally because we're not talking about directed graphs but you have to get to a vertex and then you have to leave it and you can't go back so in a cycle each vertex has degree two vertex a in this graph has a degree of one so there's no way it's going to be part of a cycle in this graph thus there's no cycle in this graph that contains a and thus there's no Hamiltonian cycle in the graph a vertex with degree 1 is often called an end vertex or a leaf if we're talking about tree graphs so this gives us another necessary condition another necessary condition for a graph to be Hamiltonian is that it can have no vertex V with a degree less than 2 if it has a degree of 1 we've got this situation here if a vertex has a degree of 0 then either the graph is disconnected which we know is not allowed for it to be hamiltonian or it's a trivial graph with just one vertex which clearly has no cycles so let's quickly before we go see a couple examples of families of graphs that are always Hamiltonian one really obvious one perhaps the most obvious one is the family of cycle grass so here's the cycle graph on three vertices this very clearly has a Hamiltonian cycle go from here to here to here to there easy same thing with if we draw another cycle say the psychograph on five vertices psycho graphs by their definition are very clearly Hamiltonian you can find a cycle in this graph that contains every vertex now certainly if a graph is Hamiltonian and we add edges to it the resulting graph will still be Hamiltonian because whatever Hamiltonian cycle was there before will still exist now this leads to the result very easily that all complete graphs with at least three vertices or Hamiltonian let's add edges to this cycle graph to make it a complete graph so here's a complete graph on five vertices and you can see clearly it's still a Hamiltonian graph because the cycle that was there before is still there let me know in the comments if you can think of any other families of graphs that are always Hamiltonian also let me know if you can think of any more necessary conditions for a graph to be Hamiltonian it can be as simple and obvious or as complex as you want I'd be interested to see what you come up with now before we go let me just leave you one example exercise oh and also I mentioned earlier there are some sufficient conditions as well for a graph to be Hamiltonian these are conditions that if a graph meets them we know its Hamiltonian but if a graph doesn't meet them we don't know that it's not Hamiltonian so we'll go over some of those in another lesson one of them is called ORS theorem which I'll hopefully have a proof I'll have a proof on that firm out pretty soon so I hope you'll subscribe so you don't miss that now let's see this example problem so here's the question k MN is the complete bipartite graph where one part I'd set has n vertices and the other part I'd set has n vertices so the question is what must be true about M in n in order for this complete bipartite graph to be Hamiltonian so let me know what you think and justify your response and you can even write a proof if you want let me know down in the comments and I will of course leave an explanation in the Crypton so I hope this video helped you understand Hamiltonian cycles grass and paths let me know in the comments if you have any questions need anything clarified or have any other video requests thank you very much for watching I'll see you next time and be sure to subscribe for the swankiest math lessons on the internet and a big thanks to valo who upon my request kindly gave me permission to use his music in my math lessons linked to his music in the description [Music] [Music]

Channel: Wrath of Math

Views: 26,190

Keywords: wrath of math, math lessons, math, education, math video, graph theory, hamiltonian cycle, hamiltonian path, hamiltonian graph, hamilton cycle, hamilton path, hamilton graph, necessary conditions hamiltonian

Id: 2UczS2hQLsI

Length: 11min 53sec (713 seconds)

Published: Sat Oct 26 2019