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!

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!

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.

********************************************************************

+WRATH OF MATH+

Follow Wrath of Math on...

[WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!

[devinnehoffmann]

Thank you so much for taking the time to post these videos on Hamiltonian Graphs. I am currently doing a project on them for my Graph Theory course at university. Your videos helped me to better understand the topic and know what to look out for to identify a graph as Hamiltonian! Very much appreciated.

[Praful]

I have a doubt, why is it deg(vo)+deg(v1)+1 shouldnt it be 2 instead of 1, since we are counting both vo an vk

[jerryjohnthomas]

Superb Man, huge thankyou. Just a small doubt can we say deg(V0) + deg(Vk) + 1(for Vk), then an additional 1 for Vo <= k+1, is this extra 1 also valid, or where is Vo getting considered. I know that this will not break but just a lower bound but just a small dbt i wanted to know. Anyways thanks a lot man

[PunmasterSTP]

Ah, another edgy proof. Hamiltoniawesome! 👍

[arturssitdikovs]

I hope your channel gonna be more popular! Thank you !

[ВладимирРублев-йг]

Why first 3 minutes of your video are proof? It works if we consider only non-adjacent vertices, and if we will take adjacent vertices Dirac's theorem will hold, but your proof won't work.

[a-pk]

I am not quite understand why deg(v0)+deg(vk)+1<=n+1.May I say in this way?
Assume no vj s.t (vjv0) and (vj-1 vk)
then all vi s.t (viv0)=> vi-1 cannot be adjacent to ak, therefore, deg(vk)<=n-1-(n/2)=n/2-1 (why n -1 because #neighbour at most n-1 (exclude itself))<n/2
contradiction

[aloofakeelah]

for a graph to be connected shouldn't minimum degree be just greater than (n-1/2)? how can we be sure even for n/2?

[CoffeewithHarshan-lcjd]

A million thanks! Can you please explain how to solve Chinese salesman problem?

[jaspergutierrez]

Can you pls explain what is vj vk v0v1

[d-rex]

You say n+1 < K+1 gives the necessary contradiction... What if n+1 = k+1?

[hitajuneja]

This made so much sense! loved this, thank you!

[detranquoc]

can u type a solution :< i'm vietnamese

[AbhishekSingh-qxkm]

Can I do it like you've done the ore's theorem? Like extending the graph till its 1 edge short to be Hamiltonian then proceeding by contradiction?

[ragilindah]

Hello mr.!!! I'm Ragil from Indonesia, activated your subtitle please, cause i need it so much :*

[speedoftheheron]

Thank you so much! This was so incredibly helpful!

[arshakkhoshnevis]

Thank you so much, it was wonderful proof