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:
https://en.wikipedia.org/wiki/Hamilto...
https://mathworld.wolfram.com/Hamilto...
https://mathworld.wolfram.com/Hamilto...
https://www.geeksforgeeks.org/mathema...

Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": https://amzn.to/48WKqfy

******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": https://amzn.to/48ZWhtj

"Graph Theory (Diestel)": https://amzn.to/4aYCSdW

******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): https://amzn.to/4aWC1dM

A Book of Abstract Algebra (Pinter): https://amzn.to/3S2QmfV

Language, Proof and Logic: https://amzn.to/47EIZkE

Linear Algebra and Its Applications: https://amzn.to/48QsoMt

All the Math You Missed: https://amzn.to/3u5dORP

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