Proof: Ore's Theorem for Hamiltonian Graphs | Sufficient Condition for Hamilton Graphs, Graph Theory

preview_player
Показать описание
What is Ore's Theorem for Hamiltonian graphs and how do we prove it? Ore's Theorem gives us a sufficient condition for a graph to have a Hamiltonian cycle and therefore be a Hamiltonian or Hamilton graph. The theorem tells us that if, in a graph with order n greater than or equal to 3, the degree sum of any pair of non-adjacent vertices is greater than or equal to n, then the graph is Hamiltonian. Put very simply, this tells us if a graph has so many edges that it fits the aforementioned conditioned, then it must be Hamiltonian.

Notice that the condition doesn't specify directly that the graph must be connected, but if a graph fulfills the condition it will inevitably be connected, and this can be easily proven. Our proof will use an argument by contradiction, a maximally-non-Hamiltonian supergraph, a Hamilton path, and more! It's a fun ride!

◉Textbooks I Like◉

★DONATE★

Thanks to Petar, dric, Rolf Waefler, Robert Rennie, Barbara Sharrock, Joshua Gray, Karl Kristiansen, Katy, Mohamad Nossier, and Shadow Master for their generous support on Patreon!

Follow Wrath of Math on...

Рекомендации по теме
Комментарии
Автор

Small correction: around 10:24 when I write out the cycle that would cause the contradiction, the second to last thing in the cycle is "2", I meant to write "v_2". Let me know if you see anything else that looks wrong or if you have any questions!

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!

WrathofMath
Автор

Fabulous explanation. I had to rewind sometimes because my brain wouldn't compute immediately.

Joachim
Автор

You are amazing at explaining concepts, thank you. I don't know what my lecturer is talking about half the time.

oSamiXD
Автор

I watched, re-watched, played, replayed to reach the point when I said "aha". Thanks for the great explanation!

ilhomsadriddinov
Автор

Thank you so much for this video! It really helped me in an exercise I was given. The observation that if an edge from x to a vertex v_i on the path exists then the edge from y to v_i-1 must not exist is beautiful in my opinion. Cool theorem!

netanelkomm
Автор

Thanks a great explanation.
I wonder could this be extended to proving that a graph G contains a Hamiltonian path if for every vertex pair (u, v) in G, deg(u) + deg(v) >=n-1 where n is the number of vertices in the graph.

harshitgupta
Автор

This was literally one of the edgiest proofs I've ever seen!

PunmasterSTP
Автор

Thank you for such a simple and clear explanation 😁

SimpleLivingHigherThinking
Автор

that is the perfect persuasive proof for ore's theorem. thank you very much

achrafBadiry
Автор

I have graph theory exam tomorrow.You really saved me!!

kathirr.m.
Автор

Thanks for the video! I came up with the idea also but your video clarified my thought process.

권민석-pj
Автор

This is really helpful bro! I can't even understand what my chinese version of text book was talking about lol.

hongyanwu
Автор

Ohh my god tq for saving my life... This was very difficult for me to understand u made it very clear.. 🤩🤩tq sir

kamali
Автор

Very clear explanation of the proof. Very professional, from a math student

sebastiand
Автор

So at 10:00 we say that our crucial observation is correct because G' cannot contain a Hamiltonian cycle but haven't we assumed that adding any additional edge to G' would make it hamitonian and that's what we are doing when we are joining y and v_i-1 by an edge?

vanshikasinghal
Автор

Thank you for all your videos. And, Could you explain also about tutte's wheel theorem? It is too hard..

골D에이스
Автор

proof follows from Pigeonhole principle, IISCR, PUNE, INDIA NPTEL lecture series explains it so well
you are also good.

SHASHANKRUSTAGII
Автор

12:34 can't we subtract another 1 for x itself?

MrRyanroberson
Автор

I'm not sure I follow why you can add edges to the graph without changing the initial assumption here, ie I'm not convinced G is Hamiltonian. From the contradiction, I'm getting that G' is Hamiltonian, but I'm not I follow how that's also the case for G.

itskshitij
Автор

WOW! I read the blob of words in my textbook for Proof of Dirac's Theorem (which rolls in Ore's Theorem into it) over and over and over, and tried to sketch out examples it did not make any sense. Your explanation captured in half a whiteboard makes it so clear now. Why can't proofs in textbooks be structured and readable, and break down the flow? It is almost as if they intentionally want to limit the number of people who can understand it, so that only "elite mathematicians" can get through them.

niazazeez