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

What are Hamiltonian cycles, graphs, and paths? Also sometimes called Hamilton cycles, Hamilton graphs, and Hamilton paths, we’ll be going over all of these topics in today’s video graph theory lesson!

A Hamilton cycle in a graph G is a cycle containing all vertices of G. A Hamilton path in G is a path containing all vertices of G. A Hamiltonian graph is a graph that contains a Hamiltonian cycle.

Hamiltonian cycles are kind of similar to Euler circuits. Euler circuits are circuits containing every edge of a graph. It’s easy to know whether or not a graph has an Euler circuit. A graph has an Euler circuit if and only if all of its vertices have even degrees. Such a nice theorem does not exist for Hamiltonian graphs. We know that a Hamiltonian graph needs to be connected, needs to have no cut vertices, and other necessary conditions, but these are not sufficient. We also know some sufficient conditions that are not necessary for a graph to be Hamiltonian.

SOLUTION TO PRACTICE PROBLEM:

The graph Kmn is Hamiltonian if and only if m = n and m is greater than 1 (which means n is greater than 1 as well). In a bipartite graph, each vertex in a cycle must be in a different partite set from the preceding vertex. If, without loss of generality, n is greater than m, then in trying to make a Hamiltonian cycle we would eventually come to the last vertex of the partite set with m vertices, then move to a vertex in the other partite set, then we would have to travel back to the partite set with n vertices, which would mean we'd be revisiting a vertex without having completed the Hamiltonian cycle, which is not allowed. In a Hamiltonian cycle we can only revisit the starting vertex after reaching every other vertex in the graph.

If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

********************************************************************

+WRATH OF MATH+

Follow Wrath of Math on...

[WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!

[minudharmasena]

I do not have words to express my gratitude towards this channel coz am covering everything on my discrete and calculus courses by this.Thank you so much sir and one small request !Plz if u can keep doing the videos lively like this not using screen and just writing because it gives a feel that we are really learning in your class.

[likithr.n]

Man what do i say to this amazing teacher, i wish the world had more teachers like you.

[Sirjio]

00:29 Hamiltonian Cycle: A Hamiltonian cycle in graph theory is a cycle that contains every vertex of the graph.
02:00 Hamiltonian Path: Deleting an edge from a Hamiltonian cycle results in a Hamiltonian path, a path that contains every vertex.
03:48 Hamiltonian Path vs. Cycle: Having a Hamiltonian path doesn't guarantee a Hamiltonian cycle; the converse is not necessarily true.
05:11 Connectivity: A necessary condition for a graph to be Hamiltonian is that it must be connected.
05:38 Cut Vertices: A graph must not have cut vertices (vertices that disconnect the graph when deleted) to have a chance of being Hamiltonian.
07:53 Degree Condition: Another necessary condition is that a graph cannot have a vertex with a degree less than 2; degree 1 vertices pose problems.
08:46 Always Hamiltonian Graphs: Cycle graphs and complete graphs (with at least three vertices) are always Hamiltonian.
10:22 Sufficient Conditions: There are sufficient conditions for a graph to be Hamiltonian, like Ore's Theorem, which will be covered in another

[Jokngar]

Wrath of Math has really drive me crazy. I can't image to might have such a gleaming and audible tutor with well oriented presentation ever. I thank you sr.

[mimicaaaa]

I'm understanding graph theory so much better from watching your videos! Thank you so much and keep up the great work :))

[KMC_Mukul]

Thank you for such and amazing and coherent lectures. They are very useful for my exams.

[ardrakozhissery]

Sir, thanks a lot. Please prove the result "Let D be a simple n-vertex digraph. Suppose that for every pair of
vertices v and w for which there is no arc from v to w, outdeg(v) + indeg(w) ≥ n. Then
D is Hamiltonian.

[sree]

for a complete bipartite graph to be a hamiltonian graph we need an equal number of vertices in each set and the minimum value of m and n have to be 2.

[Annikai]

Your videos have been a big help understanding graph theory.

[Hi_Brien]

I think I'm just going to watch this channel as my entertainment for the next few months :P by the time I get through all of this I'll be a good graph theorist (seeing as I do have homework that forces me to be as well)

[mardenge]

another condition would be the number of edge in hamaltonian is greater than or equal to n....is this correct?

[vartikasingh]

Please make a video on k edge colouring and edge multiplicity... please sir

[diannesiat]

Sir, if vertices intersect but the vertex-es are completed, is it still hamiltonian?

[kushalava]

Hello sir!
Can you please make a video on constructing Euler path....

[landonwork]

If you have a graph that is a square lattice of 3x3=9 nodes, is that a hamiltonian graph? I can't find the hamiltonian cycle even though it is connected and there are no cut vertices. A 3x4 lattice works just fine though.

[neetdiagramacticlearning]

U saved me today dude...Thanks a lot ❣️❣️

[AZ-txyd]

thank you so much for this insightful video!! it helped me out SO MUCH. thank you thank you thank you!!! but one thing i don't get is at 4:02--why can't i add a link from 4 to 1? it's similar to how You'd done the (a, b, c, d, a) cycle where a and c had a link together above b.

[russelljazzbeck]

Thanks for this. You're great at explaining it like I'm 5.

[전윤하-bi]

Could you please teach at my graph theory class? You are definetely better than my professor !