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! ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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!
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.
Thanks for watching and I am glad you found the drawing helpful! I definitely agree it is really helpful, sometimes a drawing is really critical in helping to explain what is going on in a Graph Theory proof, otherwise it can be quite challenging to make sense of all these vertices with different subscripts, and what significance they have.
So glad it helped! Thanks for watching and check out my Graph Theory playlist if you're looking for more on the topic! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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.
Thanks so much, I am glad this helped! It takes a lot of effort to understand these concepts at times. I don't know what textbook you're using, but most of my graph theory playlist is based on the book by Chartrand and Zhang. There is an affiliate link to it in the description of the video. It's a great textbook, and while some of its proofs left me scratching my head for a little while, overall they are very well done. Good luck!!
@@WrathofMath I made a mistake above, the text (which makes more sense now when I read it after watching the videos) does not roll in Ore's theorem, but proves it the same way as how you did in the latter part of the Dirac's Theorem video. I am using Chartand and Zhang too. The textbook is great. It is very lucid and engaging. It weaves the content through history, introduces interesting problems, holds the suspense for problems solved in later chapters, describes everything very clearly with examples and diagrams. But I hit a wall every time I read something that is written between "Proof:" and □. Not just is in this text, this is a general challenge I have with textbooks of proof-based courses. Channels like yours are the saving grace.
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.
What the proof contradicts is the existence of a maximally hamiltonian path with the same number of or more edges than G. Hence it proves that G is a hamiltonian cycle
You're very welcome! Thank you for watching and for your request - though I am not familiar with that theorem. I'll add it to my list and research it a bit when I can!
@@WrathofMath thank you so much. your videos were very helpful. They are the best video I've seen. I think your explanation is amazing..... I couldn't understand menger's theorem for several days. But your video makes me understand it.!!!!!!! really thank you. I'm now taking the graph theory classes in college and having trouble to understand them..
But after I've seen about 80 videos that you uploaded, I could feel fun to graph theory. Your video helped me a lot:)
Could you explain why we can add edges to original graph? I feel like if we do, we don't prove theorem that G is hamiltonian but that G' is hamiltonian and it doesn't conclude that G is also hamiltionian. For example in this proof you use the fact that there is hamiltionian path in G', but G doesn't have to also have it. Besides, very good explanation. I'm studying for my exam and your videos are very helpful, thanks a lot!
Thanks for watching and great question! Sometimes in these contradiction proofs it can be easy to lose track of where we started from once we finish. You are right that we didn't exactly show G is Hamiltonian, we showed G' is Hamiltonian, but here is why that is sufficient to prove G is Hamiltonian. We assumed, for contradiction, that there exists a graph G contradicting our desired result. So we assumed G fits our degree sum condition, but isn't Hamiltonian. It may be the case that we can add edges to G and still not have a Hamiltonian graph, so we arbitrarily add edges until the addition of any more edges would make it Hamiltonian and call this graph G'. What we are doing is saying, if this graph G exists, then this more extreme version G' also exists. We then show a contradiction regarding the degrees of G'. Thus, since the existence of G implied the existence of G', which implied a contradiction, G cannot exist. In other words, a graph contradicting our claim cannot exist. I'm very glad the lessons have been helpful. Let me know if that explanation helps or if you have any more questions! EDIT: Note that it's possible that we cannot add any edges to G without making it Hamiltonian, in which case G equals G'.
@@WrathofMath Okay, I think I understand now. When we encounter contradiction regarding the degrees of G', we're just saying that the assumption that there is 'counter-example' was wrong (not directly that G IS in fact Hamiltonian). Everything else besides this assumption was logical reasoning so it can't be wrong. Thanks! :)
@@WrathofMath I think the explanation requires a refinement. What the proof really shows is that G' has to be Hamiltonian, but the logic doesn't necessarily say that G is Hamiltonian. By G' being Hamiltonian, it must have been the case that we just cannot add to G to get G' because, somehow, adding edges caused G' to become Hamiltonian. Then we see now the logic! It must have been that G was already "maximally not Hamiltonian" which we thought was G'. Thus G is what we wanted G' to be and by the same proceeding logic, G is Hamiltonian. It feels like the video glossed over that extra step in logic. I feel that just saying "G implied G' and G' implied a contradiction" only really says that the implication just wasn't true, not that the original implier's properties somehow fails.
Hello, great video! Really helpful. I have a question, how can we be sure that a graph G' exists, meaning a graph that putting any edge would make it Hamiltonian, i mean i get it for sure but just the fact that a complete graph is hamiltonian is enough to prove it? I have an exam in 4 days and im planning on using this proof for ores theorem since the one on the book is kinda complicated for me so i want to make sure that my professor won't be weird because i used another proving method and not his. Thanks!
would please provide the proof of; Let G be a connected graph of order n ≥ 3 with vertex connectivity κ(G) and independence number α(G). Ifκ(G) ≥ α(G), thenG is Hamiltonian.
thanks sir! can you show me the proof of the this question please? i need your help! Let G be an orientation of a connected graph with at least two vertices such that every vertex v of G satisfies that its in-degree and out-degree is the same. Show that G has a closed (directed) walk containing each edge exactly once.
You're very welcome, I'm glad to help and thank you for watching! Absolutely, I may get to recording it this weekend so it would be out sometime this coming week. Give it a go yourself in the meantime! The proof we'll go over has some similarities to this one on Ore's Theorem. We'll begin with a longest path in our graph, make an argument for what must be a Hamiltonian cycle in the graph, and show that if this is not Hamiltonian as we claim it is, then we would be able to find a path longer than the path we initially assumed was the longest. So that's the back of the box summary. See you later this week for the proof and thanks for the request!
Hi, I have a question, you are trying to contradict that G isn't hamiltonian, and you come to the conclusion that the initial condition of the degree is not met for the G' graph. But how can you ensure that it is also true for G when G' it has other additional edges and has more connections?
Thanks for watching and good question! The contradiction is that if this graph G that isn't hamiltonian exists, then there also exists this other graph G' which contradicts our assumptions. This forbids the supposed graph G from existing, as it leads to a contradiction via this G' construction. You're right that we aren't necessarily contradicting a feature of G, but we are contradicting a feature of something that MUST exist if G does. Hence, G mustn't exist. Hope that helps!
@@WrathofMath If I understood good, for have a contradiction you just need an example of a non hamiltonian graph that can contradict the degrees condition. And the graph G' is exactly this example, so why don´t use since the beginning G'? That´s what I don´t understand. Greetings from Spain!
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?
Thanks for watching, Vanshika, and great question! We are not considering adding an edge at that point of the proof, what we are doing is noticing that a certain type of edge cannot be in the graph. So we're not saying "if we add this edge, this happens", we're saying "this edge cannot be in our graph, because if it were then the graph would have a Hamilton cycle, which we know it does not". We know our graph has edges, and we're identifying a type of edge we know it can't have - edges that join y to a vertex preceding a neighbor of x. Does that make sense?
Thanks for watching! This is an important part of interpreting conditional statements. Ore's theorem tells us if a certain degree sum condition is satisfied, then the graph will be Hamiltonian. This means the degree sum condition in Ore's theorem is sufficient for a graph to be Hamiltonian. However, this condition is not necessary, and the theorem says nothing about graphs that don't fit the condition. If a graph doesn't fit the condition, like C5, it may still be Hamiltonian. The degree sum condition is sufficient, but it is NOT necessary. Does that make sense?
Thank You,Your Videos really help alot. Can you make a video on this theorem: An Euler graph G is arbitrarily traceable from a vertex v in G if and only if every circuit in G contains v.
Thanks for watching! It's perfectly normal to re-watch sections multiple times for clarity, it's the great thing about video that we can do that! And this is not an easy proof, it has several tricky pieces and that part is definitely one of them.
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath I tried to prove using ore's theorem that Km,n ( complete biparitite graph with m+n >=3 ) will have hamiltonian cycle iff m=n but wasn't able to do it
The plan is to reach a contradiction about the graph G; but the contradiction we arrived at is about the graph G'. I am not sure how that still gives us a proof.
Good question! The plan is not necessarily to reach a contradiction about G, the plan is to simply reach a contradiction. By assuming, for contradiction, we have this graph G that fits our hypothesis but not our conclusion, we also surely have the graph G' obtained from G by adding edges until the addition of another edge would make G' hamiltonian. While our contradiction may be about G', it is the existence of G that gave us G' in the first place, and so the contradiction assures us our contradiction assumption must be false. Does that make sense?
@@WrathofMath 1) I thought about it again, and I think it is _specifically_ the following (which you've pointed out in the video) that explains why reaching a contradiction about graph G' assures that our assumption about G must (also) be false. As you mentioned @4:49: "If any two vertices in G' are still not adjacent (after having added more edges to G, resulting in G') then the property : For all x, y in V s.t. {x, y} not in E -> deg(x) + deg(y) >=n still holds" "since their degrees could only have increased, if they've changed at all". It is precisely this property that we are are "attacking" (i.e., show that it *can't* be true). So, yes, I understand why you'd say that we don't necessarily have to reach a contradiction about G directly. But this has to do with the way how we carefully defined G'. Specifically, G and G' have the same vertex set. 2) I don't use Patreon, but I do want to make a one-time donation? Is there a way to do so?
Those are important points indeed! We take G as our graph given from the contradiction assumption, but then make something more extreme from it - something that still has the vital property we will be contradicting, showing how not being Hamiltonian is impossible for a graph possessing that property. If that property hadn't held, that doesn't mean we couldn't perhaps reach some other contradiction, but that's not super realistic since that property is our hypothesis - so of course it's a vital part of our proof. And there is a way to do so, at this link: www.paypal.com/paypalme/wrathofmath Any donations are extremely appreciated, and sharing the videos is another way to help. Thanks for your support and let me know if you ever have any video requests!
My pleasure, thanks for watching! Let me know if you have any questions and check out my graph theory playlist for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Hi Sir! Your video helps me a lot especially how clearly you'd explain the Ore's theorem. I hope you can make a video about Bondy-Chvatal's Theorem. I can't find any vid here on yt. Thank you in advance, it will be a great help for me since I am currently working on my thesis paper. Have a great day ahead.
When you refer to G as being hamiltonian, you are referring to it having a hamiltonian cycle correct? Not referring to the hamiltonian path, just wanting clarification.
Thanks for watching and that's exactly right! I talk a bit about Hamiltonian cycles and paths both in this lesson: ua-cam.com/video/2UczS2hQLsI/v-deo.html but you're correct, a Hamiltonian graph is one with a Hamiltonian cycle!
Thanks for watching! I'll have to dig out some cobwebs on that theorem and put it in my queue of lessons, unfortunately I'm quite behind on viewer requests these days as I get so many. I will try to get to it as soon as I can, thanks for the request!
Thanks for watching! I think that is pretty trivial because by definition a Hamilton path contains all vertices of G. So if a path was longer than the Hamilton path, it'd have more vertices, so it'd have to visit every vertex of the graph (as visited by the Hamilton path) but then also...oh wait, there are no other vertices it could visit to be longer than the Hamilton path, and paths can't revisit vertices, so QED.
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!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
I watched, re-watched, played, replayed to reach the point when I said "aha". Thanks for the great explanation!
You are amazing at explaining concepts, thank you. I don't know what my lecturer is talking about half the time.
I'm so glad it helped! Thanks a lot for watching and I'm sorry to hear your lecturer has not been clear for you, I hope that improves!
Best explanation online!
Thank You!
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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!
Absolutely! Thank you for watching!
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.
Fabulous explanation. I had to rewind sometimes because my brain wouldn't compute immediately.
Glad to help - thanks for watching!
This is really helpful bro! I can't even understand what my chinese version of text book was talking about lol.
So glad it was helpful! Thanks a lot for watching!
This was literally one of the edgiest proofs I've ever seen!
Thank you, this really helped.
You’re welcome! I’m glad it helped and thank you for your support and a great suggestion!
that is the perfect persuasive proof for ore's theorem. thank you very much
Thank you!
Thank you for such a simple and clear explanation 😁
Glad to help! Thank you for watching!
That drawing was very helpful
Thanks for watching and I am glad you found the drawing helpful! I definitely agree it is really helpful, sometimes a drawing is really critical in helping to explain what is going on in a Graph Theory proof, otherwise it can be quite challenging to make sense of all these vertices with different subscripts, and what significance they have.
Thanks for the video! I came up with the idea also but your video clarified my thought process.
Very clear explanation of the proof. Very professional, from a math student
Ohh my god tq for saving my life... This was very difficult for me to understand u made it very clear.. 🤩🤩tq sir
So glad it helped! Thanks for watching and check out my Graph Theory playlist if you're looking for more on the topic! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath sure I'll continue to watch ur channel ...
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.
Thanks so much, I am glad this helped! It takes a lot of effort to understand these concepts at times. I don't know what textbook you're using, but most of my graph theory playlist is based on the book by Chartrand and Zhang. There is an affiliate link to it in the description of the video. It's a great textbook, and while some of its proofs left me scratching my head for a little while, overall they are very well done. Good luck!!
@@WrathofMath I made a mistake above, the text (which makes more sense now when I read it after watching the videos) does not roll in Ore's theorem, but proves it the same way as how you did in the latter part of the Dirac's Theorem video.
I am using Chartand and Zhang too. The textbook is great. It is very lucid and engaging. It weaves the content through history, introduces interesting problems, holds the suspense for problems solved in later chapters, describes everything very clearly with examples and diagrams. But I hit a wall every time I read something that is written between "Proof:" and □. Not just is in this text, this is a general challenge I have with textbooks of proof-based courses. Channels like yours are the saving grace.
I have graph theory exam tomorrow.You really saved me!!
So glad to hear it, hope it goes well!
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.
What the proof contradicts is the existence of a maximally hamiltonian path with the same number of or more edges than G. Hence it proves that G is a hamiltonian cycle
Thank you for all your videos. And, Could you explain also about tutte's wheel theorem? It is too hard..
You're very welcome! Thank you for watching and for your request - though I am not familiar with that theorem. I'll add it to my list and research it a bit when I can!
@@WrathofMath thank you so much.
your videos were very helpful.
They are the best video I've seen.
I think your explanation is amazing.....
I couldn't understand menger's theorem for several days.
But your video makes me understand it.!!!!!!! really thank you.
I'm now taking the graph theory classes in college and having trouble to understand them..
But after I've seen about 80 videos that you uploaded, I could feel fun to graph theory.
Your video helped me a lot:)
Messages like yours help keep me going, thank you so much for your kind words! So glad the lessons have helped and good luck in your classes!
Lifesaving YT channel :D
Glad to help!
Thanks a lot!!, Great video!! Helped me a lot
Glad to hear it, thanks for watching!
Awesome crisp explanation
Thanks for watching and I am glad it was clear! Let me know if you have any video requests!
2. Show that if G is Eulerian, then every block (see Chapter 7 for the notion of blocks) of G is Eulerian
so helpful thanks man
My pleasure, thanks for watching!
banging video mate
Thank you! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
proof follows from Pigeonhole principle, IISCR, PUNE, INDIA NPTEL lecture series explains it so well
you are also good.
Could you explain why we can add edges to original graph? I feel like if we do, we don't prove theorem that G is hamiltonian but that G' is hamiltonian and it doesn't conclude that G is also hamiltionian. For example in this proof you use the fact that there is hamiltionian path in G', but G doesn't have to also have it.
Besides, very good explanation. I'm studying for my exam and your videos are very helpful, thanks a lot!
Thanks for watching and great question! Sometimes in these contradiction proofs it can be easy to lose track of where we started from once we finish. You are right that we didn't exactly show G is Hamiltonian, we showed G' is Hamiltonian, but here is why that is sufficient to prove G is Hamiltonian.
We assumed, for contradiction, that there exists a graph G contradicting our desired result. So we assumed G fits our degree sum condition, but isn't Hamiltonian. It may be the case that we can add edges to G and still not have a Hamiltonian graph, so we arbitrarily add edges until the addition of any more edges would make it Hamiltonian and call this graph G'. What we are doing is saying, if this graph G exists, then this more extreme version G' also exists.
We then show a contradiction regarding the degrees of G'. Thus, since the existence of G implied the existence of G', which implied a contradiction, G cannot exist. In other words, a graph contradicting our claim cannot exist.
I'm very glad the lessons have been helpful. Let me know if that explanation helps or if you have any more questions!
EDIT: Note that it's possible that we cannot add any edges to G without making it Hamiltonian, in which case G equals G'.
@@WrathofMath Okay, I think I understand now. When we encounter contradiction regarding the degrees of G', we're just saying that the assumption that there is 'counter-example' was wrong (not directly that G IS in fact Hamiltonian). Everything else besides this assumption was logical reasoning so it can't be wrong. Thanks! :)
@@WrathofMath I think the explanation requires a refinement. What the proof really shows is that G' has to be Hamiltonian, but the logic doesn't necessarily say that G is Hamiltonian. By G' being Hamiltonian, it must have been the case that we just cannot add to G to get G' because, somehow, adding edges caused G' to become Hamiltonian. Then we see now the logic! It must have been that G was already "maximally not Hamiltonian" which we thought was G'. Thus G is what we wanted G' to be and by the same proceeding logic, G is Hamiltonian. It feels like the video glossed over that extra step in logic. I feel that just saying "G implied G' and G' implied a contradiction" only really says that the implication just wasn't true, not that the original implier's properties somehow fails.
Hello, great video! Really helpful.
I have a question, how can we be sure that a graph G' exists, meaning a graph that putting any edge would make it Hamiltonian, i mean i get it for sure but just the fact that a complete graph is hamiltonian is enough to prove it?
I have an exam in 4 days and im planning on using this proof for ores theorem since the one on the book is kinda complicated for me so i want to make sure that my professor won't be weird because i used another proving method and not his.
Thanks!
would please provide the proof of; Let G be a connected graph of order n ≥ 3 with vertex connectivity κ(G) and independence number α(G). Ifκ(G) ≥ α(G), thenG is Hamiltonian.
can you explain the travelling salesman problem
great video!
thanks sir!
can you show me the proof of the this question please? i need your help!
Let G be an orientation of a connected graph with at least two vertices
such that every vertex v of G satisfies that its in-degree and out-degree is
the same. Show that G has a closed (directed) walk containing each edge
exactly once.
Thank you ,buddy
Well Understood
Glad it helped!
can you make a video about Erdos Szekers proof?
Thanks a lot ! Just got an assignment where I have to proof Ores theorem. Maybe you can proof Dirak's theorem too? :D
You're very welcome, I'm glad to help and thank you for watching! Absolutely, I may get to recording it this weekend so it would be out sometime this coming week. Give it a go yourself in the meantime! The proof we'll go over has some similarities to this one on Ore's Theorem. We'll begin with a longest path in our graph, make an argument for what must be a Hamiltonian cycle in the graph, and show that if this is not Hamiltonian as we claim it is, then we would be able to find a path longer than the path we initially assumed was the longest. So that's the back of the box summary. See you later this week for the proof and thanks for the request!
Here it is! Thanks again for the request! ua-cam.com/video/S7bORlkfwsA/v-deo.html
Hi, I have a question, you are trying to contradict that G isn't hamiltonian, and you come to the conclusion that the initial condition of the degree is not met for the G' graph. But how can you ensure that it is also true for G when G' it has other additional edges and has more connections?
Thanks for watching and good question! The contradiction is that if this graph G that isn't hamiltonian exists, then there also exists this other graph G' which contradicts our assumptions. This forbids the supposed graph G from existing, as it leads to a contradiction via this G' construction.
You're right that we aren't necessarily contradicting a feature of G, but we are contradicting a feature of something that MUST exist if G does. Hence, G mustn't exist. Hope that helps!
@@WrathofMath If I understood good, for have a contradiction you just need an example of a non hamiltonian graph that can contradict the degrees condition. And the graph G' is exactly this example, so why don´t use since the beginning G'? That´s what I don´t understand. Greetings from Spain!
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?
Thanks for watching, Vanshika, and great question! We are not considering adding an edge at that point of the proof, what we are doing is noticing that a certain type of edge cannot be in the graph. So we're not saying "if we add this edge, this happens", we're saying "this edge cannot be in our graph, because if it were then the graph would have a Hamilton cycle, which we know it does not". We know our graph has edges, and we're identifying a type of edge we know it can't have - edges that join y to a vertex preceding a neighbor of x. Does that make sense?
Thank you so much. It's very helpful 😊😊
Glad it helped! You're welcome and thanks for watching!
If you consider a cyclic graph such as C5, which is Hamiltonian, then Ore's theorem doesn't hold?
Thanks for watching! This is an important part of interpreting conditional statements. Ore's theorem tells us if a certain degree sum condition is satisfied, then the graph will be Hamiltonian. This means the degree sum condition in Ore's theorem is sufficient for a graph to be Hamiltonian. However, this condition is not necessary, and the theorem says nothing about graphs that don't fit the condition. If a graph doesn't fit the condition, like C5, it may still be Hamiltonian. The degree sum condition is sufficient, but it is NOT necessary. Does that make sense?
Thank You,Your Videos really help alot.
Can you make a video on this theorem:
An Euler graph G is arbitrarily traceable from a vertex v in G if and only if every circuit in G contains v.
I had to rewatch his explanation of the condition: (for all v_i, s.t., 2
Thanks for watching! It's perfectly normal to re-watch sections multiple times for clarity, it's the great thing about video that we can do that! And this is not an easy proof, it has several tricky pieces and that part is definitely one of them.
thank you so much that helped.
Glad to hear it! Thanks for watching!
nice video ! Thanks !
You’re welcome and thank you for watching!
thanks!
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
thank you
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
This was a fantastic explanation of the proof for this theorem. Thanks a lot for making this video!
Thanks a lot, glad it was clear!
Nice one
Thanks for watching!
@@WrathofMath I tried to prove using ore's theorem that Km,n ( complete biparitite graph with m+n >=3 ) will have hamiltonian cycle iff m=n but wasn't able to do it
I guess ore’s theorem is just sufficient condition so may not be helpful in this !
The plan is to reach a contradiction about the graph G; but the contradiction we arrived at is about the graph G'. I am not sure how that still gives us a proof.
Good question! The plan is not necessarily to reach a contradiction about G, the plan is to simply reach a contradiction. By assuming, for contradiction, we have this graph G that fits our hypothesis but not our conclusion, we also surely have the graph G' obtained from G by adding edges until the addition of another edge would make G' hamiltonian. While our contradiction may be about G', it is the existence of G that gave us G' in the first place, and so the contradiction assures us our contradiction assumption must be false. Does that make sense?
@@WrathofMath
1)
I thought about it again, and I think it is _specifically_ the following (which you've pointed out in the video) that explains why reaching a contradiction about graph G' assures that our assumption about G must (also) be false.
As you mentioned @4:49: "If any two vertices in G' are still not adjacent (after having added more edges to G, resulting in G') then the property : For all x, y in V s.t. {x, y} not in E -> deg(x) + deg(y) >=n still holds"
"since their degrees could only have increased, if they've changed at all".
It is precisely this property that we are are "attacking" (i.e., show that it *can't* be true).
So, yes, I understand why you'd say that we don't necessarily have to reach a contradiction about G directly. But this has to do with the way how we carefully defined G'. Specifically, G and G' have the same vertex set.
2)
I don't use Patreon, but I do want to make a one-time donation? Is there a way to do so?
Those are important points indeed! We take G as our graph given from the contradiction assumption, but then make something more extreme from it - something that still has the vital property we will be contradicting, showing how not being Hamiltonian is impossible for a graph possessing that property. If that property hadn't held, that doesn't mean we couldn't perhaps reach some other contradiction, but that's not super realistic since that property is our hypothesis - so of course it's a vital part of our proof.
And there is a way to do so, at this link: www.paypal.com/paypalme/wrathofmath
Any donations are extremely appreciated, and sharing the videos is another way to help. Thanks for your support and let me know if you ever have any video requests!
@@WrathofMath Small donation sent. That's all I can do atm.
Cheers!
Thanks so much!
Very clear and easy to follow. Thank you so much
My pleasure, thanks for watching! Let me know if you have any questions and check out my graph theory playlist for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Hi Sir! Your video helps me a lot especially how clearly you'd explain the Ore's theorem. I hope you can make a video about Bondy-Chvatal's Theorem. I can't find any vid here on yt. Thank you in advance, it will be a great help for me since I am currently working on my thesis paper. Have a great day ahead.
When you refer to G as being hamiltonian, you are referring to it having a hamiltonian cycle correct? Not referring to the hamiltonian path, just wanting clarification.
Thanks for watching and that's exactly right! I talk a bit about Hamiltonian cycles and paths both in this lesson: ua-cam.com/video/2UczS2hQLsI/v-deo.html but you're correct, a Hamiltonian graph is one with a Hamiltonian cycle!
vah, that nailed it completely
Thanks for watching, I am glad you found it clear!
Bro ,Can you please do a video on proof of Hall's Marriage theorem,that would help me a lot.
Thanks in advance.
Thanks for watching! I'll have to dig out some cobwebs on that theorem and put it in my queue of lessons, unfortunately I'm quite behind on viewer requests these days as I get so many. I will try to get to it as soon as I can, thanks for the request!
Your thanks were three months in advance, it's here at last! ua-cam.com/video/4tu-H4ES0fk/v-deo.html
This proof almost makes it seem obvious in reterospect.
Cool
That's for sure, love this proof! And the corollary, Dirac's Theorem! ua-cam.com/video/S7bORlkfwsA/v-deo.html
thnx
You're very welcome!
Show that a Hamilton path of a graph G, if exists, is the longest path in G..
Thanks for watching! I think that is pretty trivial because by definition a Hamilton path contains all vertices of G. So if a path was longer than the Hamilton path, it'd have more vertices, so it'd have to visit every vertex of the graph (as visited by the Hamilton path) but then also...oh wait, there are no other vertices it could visit to be longer than the Hamilton path, and paths can't revisit vertices, so QED.
@@WrathofMath
How can I contact you
We have an exam on Saturday
Lol explanation......
Even you don't know how to explain a topic .. are you know this?