What are Hamiltonian Cycles and Paths? [Graph Theory]

This video explains what Hamiltonian cycles and paths are.

A Hamiltonian path is a path through a graph that visits every vertex in the graph, and visits each vertex exactly once. That is, there are no repeated vertices and there are no repeated edges, and every single vertex in the graph is visited in the path. A graph that contains a Hamiltonian path is called a traceable graph. A Hamiltonian cycle, on the other hand, is a cycle that visits every vertex in the graph. That is, it is a walk through the graph that starts and ends on the same vertex, and that visits each vertex in the graph exactly once.

As some examples of Hamiltonian graphs, we can refer to any complete graph, any cycle graph, and the graphs of platonic solids. In general, finding a Hamiltonian cycle or Hamiltonian path in a graph is extremely difficult. As such, analyzing the problem of the existence of Hamiltonian cycles or paths in certain kinds of graphs is an active research area.

Here are some links for more information:

Recommended Books:
******************************** Hypergraph Theory ********************************

******************************** Graph Theory ********************************

******************************** Misc. Undergraduate Mathematics ********************************

These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.

0:00 - Hamiltonian Paths
0:21 - Hamiltonian Cycle
1:00 - Difficulty of finding Hamiltonian paths
1:25 - Grid graph special case
2:00 - Dirac's Theorem
2:39 - Ore's Theorem
3:20 - Connection btw theorems
3:55 - Intuition for Theorems

[VitalSine]

Thanks for watching! Let me know if you have any questions or suggestions below.

[carterwoodson]

Thank you for the upload, dont see near enough vids on math topics outside algebra and calculus

Planning to do euler paths?

Thanks again!

[VitalSine]

0:00 - Hamiltonian Paths
0:21 - Hamiltonian Cycle
1:00 - Difficulty of finding Hamiltonian paths
1:25 - Grid graph special case
2:00 - Dirac's Theorem
2:39 - Ore's Theorem
3:20 - Connection btw theorems
3:55 - Intuition for Theorems

[anusha]

Thanks! It was a very clear and concise video.

[ramonperdomo]

Good explanations. Though, I see a little contradiction in one of the Hamiltonian Graphs that you showed at the beginning. According to Dirac's theorem, the degree of every vertex in the graph should be greater than or equal to n/2, though is not the case for a hamiltonian cycle you showed in the early explanation of what a hamiltonian cycle is (0:43). Vertex A has a degree of 2, n=6, which does not make 2>=3. Could you explain this please?
Great video overall though!

[recursion.]

thanks for cuting out the outro part I was about to mute my volume down 😂😂😂😂

[monoman]

my kind of channel. just found it. post plenty, please.

[isaacvr]

Nice. You should make another one with an implementation.