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 do not have words to express my gratitude towards this channel coz am covering everything on my discrete and calculus courses by this.Thank you so much sir and one small request !Plz if u can keep doing the videos lively like this not using screen and just writing because it gives a feel that we are really learning in your class.
Wrath of Math has really drive me crazy. I can't image to might have such a gleaming and audible tutor with well oriented presentation ever. I thank you sr.
00:29 Hamiltonian Cycle: A Hamiltonian cycle in graph theory is a cycle that contains every vertex of the graph. 02:00 Hamiltonian Path: Deleting an edge from a Hamiltonian cycle results in a Hamiltonian path, a path that contains every vertex. 03:48 Hamiltonian Path vs. Cycle: Having a Hamiltonian path doesn't guarantee a Hamiltonian cycle; the converse is not necessarily true. 05:11 Connectivity: A necessary condition for a graph to be Hamiltonian is that it must be connected. 05:38 Cut Vertices: A graph must not have cut vertices (vertices that disconnect the graph when deleted) to have a chance of being Hamiltonian. 07:53 Degree Condition: Another necessary condition is that a graph cannot have a vertex with a degree less than 2; degree 1 vertices pose problems. 08:46 Always Hamiltonian Graphs: Cycle graphs and complete graphs (with at least three vertices) are always Hamiltonian. 10:22 Sufficient Conditions: There are sufficient conditions for a graph to be Hamiltonian, like Ore's Theorem, which will be covered in another
I think I'm just going to watch this channel as my entertainment for the next few months :P by the time I get through all of this I'll be a good graph theorist (seeing as I do have homework that forces me to be as well)
for a complete bipartite graph to be a hamiltonian graph we need an equal number of vertices in each set and the minimum value of m and n have to be 2.
You're welcome, thanks for watching! I try to be very precise in my language and explanations, I think that's very important. And when I am not being precise, it gets thrown in the trash!
Haha I used to render my whiteboard videos with DaVinci Resolve, which had those weird glitches! I still use Resolve for the lessons not on the whiteboard, but I use Final Cut Pro for my whiteboard videos now and it has no such demons thankfully! Thanks for watching!
@@WrathofMath hehe nice. Great Videos btw. Well explained and edited. Keep up the good work and also try branching out into other subtopics as well. The internet could use those.
Sir, thanks a lot. Please prove the result "Let D be a simple n-vertex digraph. Suppose that for every pair of vertices v and w for which there is no arc from v to w, outdeg(v) + indeg(w) ≥ n. Then D is Hamiltonian.
Thank you, glad to hear it! If you're looking for more graph theory, check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thanks, Donald! If you're looking for more Graph Theory, be sure to check out my Graph Theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
God willed it! As amazing as a wonderful explanation! But me from your computer and you show your face it would be so much greater than board! Because from you computer you use different styles and you make it is easier to understand even a new born can understand from the computer! Still I do appreciate your assistance
Thank you for watching and for the kind words! I've considered combining a face cam with the digital lessons, but there are a few difficulties with that due to my set up. I do not know if I will do it in the future, but perhaps! Thanks for letting me know what you'd like to see!
If you have a graph that is a square lattice of 3x3=9 nodes, is that a hamiltonian graph? I can't find the hamiltonian cycle even though it is connected and there are no cut vertices. A 3x4 lattice works just fine though.
thank you so much for this insightful video!! it helped me out SO MUCH. thank you thank you thank you!!! but one thing i don't get is at 4:02--why can't i add a link from 4 to 1? it's similar to how You'd done the (a,b,c,d,a) cycle where a and c had a link together above b.
You're very welcome and I am so glad it helped! Thank you for watching and for your question. The context there is I had just explained that if we have a Hamiltonian cycle, we can delete an edge to have a Hamiltonian path. Don't misunderstand that though - the point is not that we can change a cycle into a path, the point is that the path is CONTAINED within the cycle. Then I show the example at 4:02, to demonstrate that having a Hamiltonian path does NOT guarantee a cycle. As you point out, we could add an edge to the path to get a Hamiltonian cycle, but that would be changing the graph. The point was that the graph contains a Hamilton path, but no Hamilton cycle, whereas if a graph contains a Hamilton cycle, it must also have a Hamilton path. Does that clear it up?
Thanks OP for asking it and thanks Wrath of Math for explaining it. I too got confused at this part. Btw your videos are helping me a lot. Thank You so much! :D
I know Im asking the wrong place but does anyone know of a tool to get back into an instagram account..? I somehow forgot my account password. I love any tips you can give me!
4:08 Isn't the converse of deleting an edge from a h.c to get a h.p adding an edge to a h.p to get a h.c ? If so isn't it possible to get a h.c b connecting the first and last vertex on the path to get a cycle?? Confused !
Thanks for watching and for the question! We have to make sure we're clear on the statement being made. This is true: If a graph contains a Hamilton cycle, then it contains a Hamilton path; since an edge can be deleted from a Hamilton cycle to obtain a Hamilton path. Then, the converse is: If a graph contains a Hamilton path, then it contains a Hamilton cycle. The converse is not true because a graph can contain a Hamilton path without having a Hamilton cycle. Consider any path graph, for example. They all have Hamilton paths, but none of them have Hamilton cycles. So you're right we can add an edge to a Hamilton path to get a Hamilton cycle, but that edge isn't guaranteed to be there in a graph that has a Hamilton path, does that make sense? We're talking about these structures being in graphs, not just about the structures themselves.
Thanks for watching, Bharatha! I'd be happy to do a video about girth, but what specifically do you want to know relating to girth and 4-regular graphs?
Thanks for the clarification! Are you sure you've stated the result correctly? As it stands, the result is not true. Consider two K3 graphs, with one shared vertex (as if we drew two triangles that share a single vertex). The minimum degree is 2, there are 5 vertices, but no Hamilton cycle (we'd have to travel across the shared vertex multiple times if we tried to visit every vertex in the graph.
Good day sir, i have a question, I hope you can help me,, If the two graphs, A and B are both Hamiltonian, how to prove that the join of these two graphs is also Hamiltonian?
What set of assumptions are you working with? Are you assuming A and B are completely different graphs? There are three importantly different cases I can think of. 1. A and B are completely disjoint graphs, they have no vertices in common and thus no edges in common. 2. The vertex set of A is a subset of the vertex set of B (or vice versa). 3. A and B have some vertices in common, but neither vertex set is a subset of the other. If you're trying to prove the result in the first situation (which I am guessing is most likely), you want to try constructing a Hamiltonian cycle in A join B by traversing the Hamiltonian cycle you know exists in A, but right before you finish the cycle, go to the Hamilton cycle of B, which you know you can do because every vertex of A is adjacent to every vertex of B when they are joined. Then travel through the Hamilton cycle of B but right before finishing it, finish your big Hamilton cycle by returning to the vertex of A that you began at. If you're trying to prove the result in the second situation, it is fairly trivial. Say every vertex of A is also a vertex of B. Then B is a spanning subgraph of A join B, and so since B is Hamiltonian, we know A join B is also Hamiltonian. If you're trying to prove the third result, that is definitely a bit messier. I'm not immediately sure how to go about it, maybe induction on the number of vertices A and B have in common, but I'm not sure that would be helpful or necessary, since it may be difficult to use our induction hypothesis in that sort of situation.
Thanks for watching and that's funny! It's a fine looking set, but I find some of the pieces a little weird. Like the knight has a rounded bottom rather than a flat one. It can rock around a little bit on the board, which is quite odd since none of the other pieces are like that.
can you please solve this question ? Prove or give a counterexample: If every vertex has at least 3 neighbors, then the graph has a cycle of length at least 4, i.e., a cycle consisting of at least 4 vertices.
Thanks for the question! Here are two lessons in which we use ideas similar to that necessary to prove your claim. Result about paths: ua-cam.com/video/7bBTpSVa9tc/v-deo.html Result about minimum degree implying a cycle: ua-cam.com/video/FLqeKSAPlwM/v-deo.html A lesson proving a generalization of your claim comes out two and a half hours from now! So give it a try yourself and then check out the lesson when it comes out! :) If you're not subscribed already, you can subscribe to make sure you see it in your feed.
@@WrathofMath I watched this video but it's getting mix up , can you please give any example related to algorithm that you explained in this video. thanks
@@WrathofMath I watched second video also but it's like explaining there is a cycle but my question is about , if a vertex has n neighbors then cycle is of n+1 vertices , in my mind I can do it with 1 vertex having 3 neighbors but to make a cycle there must be a path between every adjacent vertices.
Thanks for watching! I mention complete bipartite graphs at the end of the video, and in the description I provide an explanation as to what complete bipartite graphs are Hamiltonian and why. Would you like a lesson on this topic?
After over 350 videos, you're the first person to make reference to what I have been saying at the end of every single lesson! It made me smile to see that!
Design a graph that has a Hamiltonian cycle but does not have an Euler tour. You need to explain why the graph has no Euler tour. can anybody help me to solve this question?
Thanks for watching and what is the definition of Euler tour you're using? Do you mean a walk in the graph that contains every edge exactly once (often called an Euler path)? Or do you mean a closed walk in the graph that contains every edge exactly once (often called an Euler circuit)? Or something else?
Consider any normal cycle, and then consider Euler's circuit theorem we prove here: ua-cam.com/video/wC99T3aVDKQ/v-deo.html If we have a cycle (every cycle is 2-regular), and then add any edge to it, joining nonadjacent vertices, it is still Hamiltonian (just travel around the outer edges of the cycle), but it is not Eulerian since two of our vertices have odd degree (the ones we added an edge between). Does that help?
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 do not have words to express my gratitude towards this channel coz am covering everything on my discrete and calculus courses by this.Thank you so much sir and one small request !Plz if u can keep doing the videos lively like this not using screen and just writing because it gives a feel that we are really learning in your class.
Man what do i say to this amazing teacher, i wish the world had more teachers like you.
Thanks for your support likith! The nice thing is we have the internet so many teachers are available to people all over the world!
@@WrathofMath if you had focussed and made math lessons catered to students in India. I guarantee u would have millions of subscribers
Wrath of Math has really drive me crazy. I can't image to might have such a gleaming and audible tutor with well oriented presentation ever. I thank you sr.
Thanks so much! Let me know if you ever have any questions!
00:29 Hamiltonian Cycle: A Hamiltonian cycle in graph theory is a cycle that contains every vertex of the graph.
02:00 Hamiltonian Path: Deleting an edge from a Hamiltonian cycle results in a Hamiltonian path, a path that contains every vertex.
03:48 Hamiltonian Path vs. Cycle: Having a Hamiltonian path doesn't guarantee a Hamiltonian cycle; the converse is not necessarily true.
05:11 Connectivity: A necessary condition for a graph to be Hamiltonian is that it must be connected.
05:38 Cut Vertices: A graph must not have cut vertices (vertices that disconnect the graph when deleted) to have a chance of being Hamiltonian.
07:53 Degree Condition: Another necessary condition is that a graph cannot have a vertex with a degree less than 2; degree 1 vertices pose problems.
08:46 Always Hamiltonian Graphs: Cycle graphs and complete graphs (with at least three vertices) are always Hamiltonian.
10:22 Sufficient Conditions: There are sufficient conditions for a graph to be Hamiltonian, like Ore's Theorem, which will be covered in another
very well explained, thank you
Thanks for watching Ahmed, and I am glad it was clear!
I'm understanding graph theory so much better from watching your videos! Thank you so much and keep up the great work :))
I think I'm just going to watch this channel as my entertainment for the next few months :P by the time I get through all of this I'll be a good graph theorist (seeing as I do have homework that forces me to be as well)
for a complete bipartite graph to be a hamiltonian graph we need an equal number of vertices in each set and the minimum value of m and n have to be 2.
Indeed! 🎉
Thank you for such and amazing and coherent lectures. They are very useful for my exams.
Glad to help!
Your videos have been a big help understanding graph theory.
So glad to hear that, thanks for watching!
So clearly expalined,Thanks!
Please make a video on k edge colouring and edge multiplicity... please sir
Thanks for this. You're great at explaining it like I'm 5.
You're welcome, thanks for watching! I try to be very precise in my language and explanations, I think that's very important. And when I am not being precise, it gets thrown in the trash!
0:16 that dementor damn near killed him
Haha I used to render my whiteboard videos with DaVinci Resolve, which had those weird glitches! I still use Resolve for the lessons not on the whiteboard, but I use Final Cut Pro for my whiteboard videos now and it has no such demons thankfully! Thanks for watching!
@@WrathofMath hehe nice. Great Videos btw. Well explained and edited. Keep up the good work and also try branching out into other subtopics as well. The internet could use those.
U saved me today dude...Thanks a lot ❣️❣️
This video was Hamiltoniawesome!
Oh my god, what a teacher❤
another condition would be the number of edge in hamaltonian is greater than or equal to n....is this correct?
Thanks for a video! I like your pronunciation of "Hamiltonian cycle" :D
Could you please teach at my graph theory class? You are definetely better than my professor !
Sir, thanks a lot. Please prove the result "Let D be a simple n-vertex digraph. Suppose that for every pair of
vertices v and w for which there is no arc from v to w, outdeg(v) + indeg(w) ≥ n. Then
D is Hamiltonian.
really appreciate the 4k thanks
Appreciate your appreciation. I have stacks and stacks of hard drives to store these 4K vids, gonna need a warehouse eventually!
Good work .It will help me preparing for exams
Thank you, glad to hear it! If you're looking for more graph theory, check out my graph theory playlist!
ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
5 stars for teaching.
Thanks, Donald! If you're looking for more Graph Theory, be sure to check out my Graph Theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
thanks for your efforts
Thanks for watching!
Great video sir, Thank you very much
You're very welcome, I am glad it helped and thanks for watching!
Hello sir!
Can you please make a video on constructing Euler path....
This is very good🎉
Thank you!
Life saver ❤
Sir, if vertices intersect but the vertex-es are completed, is it still hamiltonian?
God willed it! As amazing as a wonderful explanation! But me from your computer and you show your face it would be so much greater than board! Because from you computer you use different styles and you make it is easier to understand even a new born can understand from the computer! Still I do appreciate your assistance
Thank you for watching and for the kind words! I've considered combining a face cam with the digital lessons, but there are a few difficulties with that due to my set up. I do not know if I will do it in the future, but perhaps! Thanks for letting me know what you'd like to see!
honorable! Be grateful for your thoughtfulness! Glory is due to God!
Hi guys, so if there's only one node and a loop edge, does that always show the Hamilton graph?
Please make videos regrding complex analysis
so much i got here, thank you
I’m glad it helped, thanks for watching, Phill!
If you have a graph that is a square lattice of 3x3=9 nodes, is that a hamiltonian graph? I can't find the hamiltonian cycle even though it is connected and there are no cut vertices. A 3x4 lattice works just fine though.
Okay, so I find your video on Ore's theorem and now I get the difference between necessary conditions and sufficient conditions.
Born to lecture
Thank you - I work very hard at clarity in my lessons! Let me know if you ever have any questions!
Amaaaazing🔥🔥🔥🔥🔥🔥
Thank you!
thank you so much for this insightful video!! it helped me out SO MUCH. thank you thank you thank you!!! but one thing i don't get is at 4:02--why can't i add a link from 4 to 1? it's similar to how You'd done the (a,b,c,d,a) cycle where a and c had a link together above b.
You're very welcome and I am so glad it helped! Thank you for watching and for your question. The context there is I had just explained that if we have a Hamiltonian cycle, we can delete an edge to have a Hamiltonian path. Don't misunderstand that though - the point is not that we can change a cycle into a path, the point is that the path is CONTAINED within the cycle. Then I show the example at 4:02, to demonstrate that having a Hamiltonian path does NOT guarantee a cycle. As you point out, we could add an edge to the path to get a Hamiltonian cycle, but that would be changing the graph. The point was that the graph contains a Hamilton path, but no Hamilton cycle, whereas if a graph contains a Hamilton cycle, it must also have a Hamilton path. Does that clear it up?
@@WrathofMath ohmygod yes that does clear it up nicely, thank you!
Thanks OP for asking it and thanks Wrath of Math for explaining it. I too got confused at this part. Btw your videos are helping me a lot. Thank You so much! :D
I know Im asking the wrong place but does anyone know of a tool to get back into an instagram account..?
I somehow forgot my account password. I love any tips you can give me!
@Drew Thomas instablaster ;)
Thank you
You're welcome! Thanks for watching!
Hamiltonian Acyclic Graph vs Euler Acyclic Graph what is the difference?
if i were to ever see you at a restaurant, i would pay for all your bills.
4:08 Isn't the converse of deleting an edge from a h.c to get a h.p adding an edge to a h.p to get a h.c ? If so isn't it possible to get a h.c b connecting the first and last vertex on the path to get a cycle?? Confused !
Thanks for watching and for the question! We have to make sure we're clear on the statement being made. This is true: If a graph contains a Hamilton cycle, then it contains a Hamilton path; since an edge can be deleted from a Hamilton cycle to obtain a Hamilton path.
Then, the converse is: If a graph contains a Hamilton path, then it contains a Hamilton cycle.
The converse is not true because a graph can contain a Hamilton path without having a Hamilton cycle. Consider any path graph, for example. They all have Hamilton paths, but none of them have Hamilton cycles. So you're right we can add an edge to a Hamilton path to get a Hamilton cycle, but that edge isn't guaranteed to be there in a graph that has a Hamilton path, does that make sense? We're talking about these structures being in graphs, not just about the structures themselves.
If G is hamiltonian, then L(G) is hamiltonian. How do I demonstrate this?
Can u explain about girth of 4 regular graph
Thanks for watching, Bharatha! I'd be happy to do a video about girth, but what specifically do you want to know relating to girth and 4-regular graphs?
Superb video sir.
Can you plz solve this problem :
Prove G is Hamilton if p>=3 and δ>=p/2
Thanks for watching and can you clarify your question? What is p? And I assume δ is the minimum degree?
@@WrathofMath
Here p is denoted as vertices sir.
Thanks for the clarification! Are you sure you've stated the result correctly? As it stands, the result is not true. Consider two K3 graphs, with one shared vertex (as if we drew two triangles that share a single vertex). The minimum degree is 2, there are 5 vertices, but no Hamilton cycle (we'd have to travel across the shared vertex multiple times if we tried to visit every vertex in the graph.
I am preparing the SHSAT,good luck for me
That's awesome! I wish you the best of luck!
Wrath of Math thank you😀
For (K m,n)
m=n for all m,n >=2 for the graph to be Hamilton
Thanks for watching and you're exactly right!
Good day sir, i have a question, I hope you can help me,,
If the two graphs, A and B are both Hamiltonian, how to prove that the join of these two graphs is also Hamiltonian?
Thanks for watching and for your question! By "the join" of A and B, do you mean the graph created by joining every vertex of A to every vertex of B?
@@WrathofMath yes sir
@@WrathofMath im having a hard time on proving it, huhu
What set of assumptions are you working with? Are you assuming A and B are completely different graphs? There are three importantly different cases I can think of.
1. A and B are completely disjoint graphs, they have no vertices in common and thus no edges in common.
2. The vertex set of A is a subset of the vertex set of B (or vice versa).
3. A and B have some vertices in common, but neither vertex set is a subset of the other.
If you're trying to prove the result in the first situation (which I am guessing is most likely), you want to try constructing a Hamiltonian cycle in A join B by traversing the Hamiltonian cycle you know exists in A, but right before you finish the cycle, go to the Hamilton cycle of B, which you know you can do because every vertex of A is adjacent to every vertex of B when they are joined. Then travel through the Hamilton cycle of B but right before finishing it, finish your big Hamilton cycle by returning to the vertex of A that you began at.
If you're trying to prove the result in the second situation, it is fairly trivial. Say every vertex of A is also a vertex of B. Then B is a spanning subgraph of A join B, and so since B is Hamiltonian, we know A join B is also Hamiltonian.
If you're trying to prove the third result, that is definitely a bit messier. I'm not immediately sure how to go about it, maybe induction on the number of vertices A and B have in common, but I'm not sure that would be helpful or necessary, since it may be difficult to use our induction hypothesis in that sort of situation.
Just remember Lewis Hamilton cycles touching every apex but not necessarily every edge coz he cuts the corners
Or he over extends
m has to be equal to n
ive got the exact same chess set as you, nice
Thanks for watching and that's funny! It's a fine looking set, but I find some of the pieces a little weird. Like the knight has a rounded bottom rather than a flat one. It can rock around a little bit on the board, which is quite odd since none of the other pieces are like that.
6:20 ONE PIECE MENTIONED!!!
can you please solve this question ?
Prove or give a counterexample: If every vertex has at least 3 neighbors, then the graph has a
cycle of length at least 4, i.e., a cycle consisting of at least 4 vertices.
Thanks for the question! Here are two lessons in which we use ideas similar to that necessary to prove your claim.
Result about paths: ua-cam.com/video/7bBTpSVa9tc/v-deo.html
Result about minimum degree implying a cycle: ua-cam.com/video/FLqeKSAPlwM/v-deo.html
A lesson proving a generalization of your claim comes out two and a half hours from now! So give it a try yourself and then check out the lesson when it comes out! :) If you're not subscribed already, you can subscribe to make sure you see it in your feed.
@@WrathofMath I watched this video but it's getting mix up , can you please give any example related to algorithm that you explained in this video. thanks
@@WrathofMath I watched second video also but it's like explaining there is a cycle but my question is about , if a vertex has n neighbors then cycle is of n+1 vertices , in my mind I can do it with 1 vertex having 3 neighbors but to make a cycle there must be a path between every adjacent vertices.
This lesson proves a generalized version of your statement: ua-cam.com/video/-8QRcpbI6J8/v-deo.html
Let me know if you have any questions!
Sir, what about complete bipartite graph?
Thanks for watching! I mention complete bipartite graphs at the end of the video, and in the description I provide an explanation as to what complete bipartite graphs are Hamiltonian and why. Would you like a lesson on this topic?
Sure, sir! Can't wait for another swankiest math lesson.
After over 350 videos, you're the first person to make reference to what I have been saying at the end of every single lesson! It made me smile to see that!
@@WrathofMath 😂 Thanks, sir. Maybe, you can use the word "dope-est". (just kidding)
👍
Thanks for watching!
👍🏾
Design a graph that has a Hamiltonian cycle but does not have an Euler tour.
You need to explain why the graph has no Euler tour. can anybody help me to solve this question?
Thanks for watching and what is the definition of Euler tour you're using? Do you mean a walk in the graph that contains every edge exactly once (often called an Euler path)? Or do you mean a closed walk in the graph that contains every edge exactly once (often called an Euler circuit)? Or something else?
@@WrathofMath euler circuit
Consider any normal cycle, and then consider Euler's circuit theorem we prove here: ua-cam.com/video/wC99T3aVDKQ/v-deo.html
If we have a cycle (every cycle is 2-regular), and then add any edge to it, joining nonadjacent vertices, it is still Hamiltonian (just travel around the outer edges of the cycle), but it is not Eulerian since two of our vertices have odd degree (the ones we added an edge between). Does that help?
m=n
K(m,n) where m=n and m >=2 is always Hamiltonian
Thanks for watching and that is true! I did a lesson on it here: ua-cam.com/video/s9JoNrPzN9Q/v-deo.html
0:17 :o