Proof: Dirac's Theorem for Hamiltonian Graphs | Hamiltonian Cycles, Graph Theory

Dirac’s theorem for Hamiltonian graphs tells us that if a graph of order n greater than or equal to 3 has a minimum degree greater than or equal to half of n, then the graph is Hamiltonian. In today’s video graph theory lesson, we’ll prove Dirac’s theorem. In fact, we will give two proofs of Dirac’s theorem!

The first is rather boring. Dirac’s theorem is a corollary following easily from Ore’s theorem, another sufficient condition for a graph to be Hamiltonian. The theorem and its proof have some similarity to Dirac’s theorem. Check out my lesson on the proof of Ore’s theorem here:    • Proof: Ore's Theorem for Hamiltonian ...  

This proof isn’t too complicated, but it does have a lot of little arguments in it that add up to make a decently meaty proof overall. The first assertion we make is that a graph of order n greater than or equal to 3 with minimum degree greater than or equal to n/2 must be connected. This is easily proven (check out the lesson on it here:    • Proof: Degree Sum Condition for Conne...  ). Two vertices may be adjacent, in which case they are clearly connected. If they are not adjacent, call them x and y and notice the sum of their degrees is greater than or equal to n/2 + n/2 = n. Thus, there are n edges going from x or y to the other n-2 vertices in the graph (since no edge is joining x and y). Hence, some vertex must be adjacent to both x and y. Thus, they are connected and so is the graph.

Other arguments we make will also involve the degrees of the vertices, as well as a longest path, edges that must exist that force a cycle to exist, and of course the big one: once we find a cycle we make an argument that the cycle contains all vertices of the graph! That’s when we pull out the trap card we drew in the beginning of the proof, that our graph is connected! That gets us most of the way to the finish line. It’s a fun one!

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