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://mathworld.wolfram.com/HamiltonianPath.html#:~:text=A%20Hamiltonian%20path%2C%20also%20called,cycle%20(or%20Hamiltonian%20cycle).

https://en.wikipedia.org/wiki/Hamiltonian_path

https://mathworld.wolfram.com/HamiltonianCycle.html

https://mathworld.wolfram.com/HamiltonianGraph.html

https://www.geeksforgeeks.org/mathematics-euler-hamiltonian-paths/

Thanks for watching! Please let me know in the comments if you have any questions or feedback. ... https://www.youtube.com/watch?v=pTUVll8lcEQ