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!

PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ



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.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic