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! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
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.
@@WrathofMath Is there anyway possible you could explain the difference between necessary and sufficient conditions and what the conditions are? I know the three necessary conditions because you discussed it in your video.
You're very welcome, and thank you! I trust it will continue to grow so long as I continue to make the best lessons I can. If you know anyone who might benefit from my lessons, please do pass them along and that will help the channel grow! For now, I am continuing to enjoy being able to respond to every comment I receive, but it is getting harder. Appreciate your support!
Thanks for watching and great question! You said “deg(v0) + deg(v1) + 1” but I am assuming you meant to write deg(v0) + deg(vk) + 1. The +1 counts vk, and we are actually counting v0 with deg(v0). I know that is a bit unintuitive, but it is because for each neighbor of v0, the preceding vertex cannot be adjacent to vk. One of the possible neighbors of v0 is v1, so we are counting the preceding vertex - v0 - as a vertex that vk cannot be adjacent to. Then deg(vk) counts all the vertices that vk IS adjacent to, and then +1 counts vk. We know at least that many vertices are on the path. Does that help?
@@WrathofMath And the last vertex to which V is neighbour to is not counted , So the total number of vertex Vk cannot be neighbour to is - Degree of Vo + Vo - Last vertex Vj = Degree of Vo Isnt it
Did you read my original reply to Praful's comment? I explained it in that reply, but let me try to reiterate it here. This is discussed in a contradiction section of the proof. We suppose there is no Hamilton cycle. Thus we know that any neighbor of v0 cannot be immediately preceded by a neighbor of vk in the path, otherwise we would have a Hamilton cycle. Then, when counting the vertices on the path, even though deg(v0) is the number of neighbors v0 has, we aren't using deg(v0) to count v0's neighbors. Remember that any neighbor of v0 CANNOT be preceded by a neighbor of vk in the path. So we actually use deg(v0) to count the vertices that precede neighbors of v0, this way we count up only vertices that are not neighbors of vk, and so when we add deg(vk) to this count, we know we haven't double counted any. So again, deg(v0) is being used in this proof to count the vertices that precede neighbors of v0 on the path. One neighbor of v0 is v1, which is preceded by v0 on the path, and so deg(v0) is counting v0. Does that help at all?
@@WrathofMath thanks ALOT! I'm doing a bachelor in data science and this Playlist has been literally saving me this period. I love the way you approach this providing concrete proofs. I mostly would pick a related thesis. 😊😊
Thanks for watching Ragil! My videos don't have subtitles aside from the auto-generated RUclips captions. I try to speak very clearly so those are probably okay. You can turn them on using the "CC" button on the video player, which stands for closed captions. Hope that is some help!
Mr. can you show me how the condition of the graphs satisfies the dirac theorem? I want to know that my understanding about dirac's theorem is right or wrong.
This is probably the trickiest part of the proof, and I don't know if a plaintext description will help, but I'll give it a try. At this point in the proof, we just claimed that a Hamiltonian cycle exists, made up primarily of that path P. If v0 is adjacent to vk then there is our cycle and we're done. If that's not the case, then the only way we'd get a Hamilton cycle is if vk is adjacent to some vj and v0 is adjacent to vj+1. Thus, if we suppose for contradiction that we don't have a cycle, then the aforementioned vj and vj+1 must not exist. Supposing such a vj and vj+1 do not exist causes a contradiction, because this means that any time v0 is adjacent to some vertex vj+1, vk must NOT be adjacent to vj. So every neighbor of v0 gives us a non-neighbor of vk. But since all deg(v0) of the neighbors of v0 lie on the path, and also all the deg(vk) neighbors of vk lie on the path, and also vk lies on the path, we have that at least (n/2) + (n/2) + 1 vertices must lie on the path, and perhaps more. This is too many, since it exceeds the order of the graph. When we write deg(v0) + deg(vk) + 1 in the proof, it's important to recognize that deg(v0) is not actually there to count the neighbors of v0, it is there to count the NON-neighbors of vk, because as we said earlier each neighbor of v0 gives us a non-neighbor of vk. All of these non-neighbors must lie on the path, and certainly the actual deg(vk) neighbors of vk also lie on the path.
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.
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!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
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.
So glad the lessons have been helpful! Thanks a lot for watching, Devinne! Let me know if you ever have any video requests!
@@WrathofMath Is there anyway possible you could explain the difference between necessary and sufficient conditions and what the conditions are? I know the three necessary conditions because you discussed it in your video.
I hope your channel gonna be more popular! Thank you !
You're very welcome, and thank you! I trust it will continue to grow so long as I continue to make the best lessons I can. If you know anyone who might benefit from my lessons, please do pass them along and that will help the channel grow! For now, I am continuing to enjoy being able to respond to every comment I receive, but it is getting harder. Appreciate your support!
@@WrathofMath I definitely gonna do recommend you :)
Superb Man, huge thankyou. Just a small doubt can we say deg(V0) + deg(Vk) + 1(for Vk) , then an additional 1 for Vo
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
Thanks for watching and great question! You said “deg(v0) + deg(v1) + 1” but I am assuming you meant to write deg(v0) + deg(vk) + 1. The +1 counts vk, and we are actually counting v0 with deg(v0). I know that is a bit unintuitive, but it is because for each neighbor of v0, the preceding vertex cannot be adjacent to vk. One of the possible neighbors of v0 is v1, so we are counting the preceding vertex - v0 - as a vertex that vk cannot be adjacent to. Then deg(vk) counts all the vertices that vk IS adjacent to, and then +1 counts vk. We know at least that many vertices are on the path. Does that help?
@@WrathofMath Yep, Understood. Thank You!
@@WrathofMath And the last vertex to which V is neighbour to is not counted , So the total number of vertex Vk cannot be neighbour to is - Degree of Vo + Vo - Last vertex Vj = Degree of Vo Isnt it
@@WrathofMath how can deg(v0) include the vertex v0 itself.
Did you read my original reply to Praful's comment? I explained it in that reply, but let me try to reiterate it here. This is discussed in a contradiction section of the proof. We suppose there is no Hamilton cycle. Thus we know that any neighbor of v0 cannot be immediately preceded by a neighbor of vk in the path, otherwise we would have a Hamilton cycle. Then, when counting the vertices on the path, even though deg(v0) is the number of neighbors v0 has, we aren't using deg(v0) to count v0's neighbors. Remember that any neighbor of v0 CANNOT be preceded by a neighbor of vk in the path. So we actually use deg(v0) to count the vertices that precede neighbors of v0, this way we count up only vertices that are not neighbors of vk, and so when we add deg(vk) to this count, we know we haven't double counted any. So again, deg(v0) is being used in this proof to count the vertices that precede neighbors of v0 on the path. One neighbor of v0 is v1, which is preceded by v0 on the path, and so deg(v0) is counting v0. Does that help at all?
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?
This made so much sense! loved this, thank you!
I am not quite understand why deg(v0)+deg(vk)+1 vi-1 cannot be adjacent to ak, therefore, deg(vk)
A million thanks! Can you please explain how to solve Chinese salesman problem?
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?
excellent explanation
Thank you! I am glad it was clear!
Can you pls explain what is vj vk v0v1
Thank you so much! This was so incredibly helpful!
You're very welcome! I am glad it helped and thanks for watching!
loved this video! THANKS!!!
Glad to help, thanks for watching! If you're looking for more graph theory, check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@@WrathofMath thanks ALOT! I'm doing a bachelor in data science and this Playlist has been literally saving me this period. I love the way you approach this providing concrete proofs. I mostly would pick a related thesis. 😊😊
You say n+1 < K+1 gives the necessary contradiction... What if n+1 = k+1?
-> cycle
Hello mr.!!! I'm Ragil from Indonesia, activated your subtitle please, cause i need it so much :*
Thanks for watching Ragil! My videos don't have subtitles aside from the auto-generated RUclips captions. I try to speak very clearly so those are probably okay. You can turn them on using the "CC" button on the video player, which stands for closed captions. Hope that is some help!
Mr. can you show me how the condition of the graphs satisfies the dirac theorem? I want to know that my understanding about dirac's theorem is right or wrong.
Thank you
It was great :)
Glad to hear it, thanks for watching!
Bro You are Awesome !!!.Genius..
Thanks a lot for watching! It is a very ingenious proof, and a wonderful theorem!
Thanks alot
Glad to help!
Thank you so much, it was wonderful proof
You're very welcome, thanks for watching!
Sir , what about a graph with loop?
Ah, another edgy proof. Hamiltoniawesome! 👍
cant make sense of this part: 7:50
This is probably the trickiest part of the proof, and I don't know if a plaintext description will help, but I'll give it a try.
At this point in the proof, we just claimed that a Hamiltonian cycle exists, made up primarily of that path P. If v0 is adjacent to vk then there is our cycle and we're done. If that's not the case, then the only way we'd get a Hamilton cycle is if vk is adjacent to some vj and v0 is adjacent to vj+1. Thus, if we suppose for contradiction that we don't have a cycle, then the aforementioned vj and vj+1 must not exist.
Supposing such a vj and vj+1 do not exist causes a contradiction, because this means that any time v0 is adjacent to some vertex vj+1, vk must NOT be adjacent to vj. So every neighbor of v0 gives us a non-neighbor of vk. But since all deg(v0) of the neighbors of v0 lie on the path, and also all the deg(vk) neighbors of vk lie on the path, and also vk lies on the path, we have that at least (n/2) + (n/2) + 1 vertices must lie on the path, and perhaps more. This is too many, since it exceeds the order of the graph.
When we write deg(v0) + deg(vk) + 1 in the proof, it's important to recognize that deg(v0) is not actually there to count the neighbors of v0, it is there to count the NON-neighbors of vk, because as we said earlier each neighbor of v0 gives us a non-neighbor of vk. All of these non-neighbors must lie on the path, and certainly the actual deg(vk) neighbors of vk also lie on the path.
@@WrathofMath omg you actually replied. Thank you very much!!
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.
can u type a solution :< i'm vietnamese