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! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I got this proof in today's discrete mathematics oral exam, and I knew it only bacause I watched this video. Huge thanks to you for this clear and concise explanation!
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!
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
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.
So glad it helped! Thanks for watching and check out my Graph Theory playlist if you're looking for more on the topic! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Very nice explanation! But I didnt understand why solving the extreme case solves the question at hand. in any graph that satisfies the given degree condition there could be a case where no hamiltonian paths exist , wont the proof break down here?
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.
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.
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.
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?
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:)
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!
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
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.
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.
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!
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!
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.
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.
@@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
My pleasure, thanks for watching! Let me know if you have any questions and check out my graph theory playlist for more! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
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: ruclips.net/video/2UczS2hQLsI/видео.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!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I got this proof in today's discrete mathematics oral exam, and I knew it only bacause I watched this video. Huge thanks to you for this clear and concise explanation!
Fabulous explanation. I had to rewind sometimes because my brain wouldn't compute immediately.
Glad to help - thanks for watching!
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!
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!
I watched, re-watched, played, replayed to reach the point when I said "aha". Thanks for the great explanation!
Eureka!
Best explanation online!
Thank You!
My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
This was literally one of the edgiest proofs I've ever seen!
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.
that is the perfect persuasive proof for ore's theorem. thank you very much
Thank you!
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!
I have graph theory exam tomorrow.You really saved me!!
So glad to hear it, hope it goes well!
Very clear explanation of the proof. Very professional, from a math student
Thank you for such a simple and clear explanation 😁
Glad to help! Thank you for watching!
Thank you, this really helped.
You’re welcome! I’m glad it helped and thank you for your support and a great suggestion!
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! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@@WrathofMath sure I'll continue to watch ur channel ...
Thanks for the video! I came up with the idea also but your video clarified my thought process.
Very nice explanation! But I didnt understand why solving the extreme case solves the question at hand. in any graph that satisfies the given degree condition there could be a case where no hamiltonian paths exist , wont the proof break down here?
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.
Awesome crisp explanation
Thanks for watching and I am glad it was clear! Let me know if you have any video requests!
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.
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.
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?
proof follows from Pigeonhole principle, IISCR, PUNE, INDIA NPTEL lecture series explains it so well
you are also good.
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!
Thanks a lot!!, Great video!! Helped me a lot
Glad to hear it, thanks for watching!
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!
can you explain the travelling salesman problem
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
so helpful thanks man
My pleasure, thanks for watching!
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.
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.
2. Show that if G is Eulerian, then every block (see Chapter 7 for the notion of blocks) of G is Eulerian
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!
banging video mate
Thank you! If you're looking for more graph theory, check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
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! ruclips.net/video/S7bORlkfwsA/видео.html
great video!
Thank you so much. It's very helpful 😊😊
Glad it helped! You're welcome and thanks for watching!
can you make a video about Erdos Szekers proof?
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!
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.
12:34 can't we subtract another 1 for x itself?
... and as a result could we make a weaker constraint that deg(x)+deg(y)>=n-1?
Thank you ,buddy
Well Understood
Glad it helped!
thank you so much that helped.
Glad to hear it! Thanks for watching!
nice video ! Thanks !
You’re welcome and thank you for watching!
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.
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 !
vah, that nailed it completely
Thanks for watching, I am glad you found it clear!
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! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
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: ruclips.net/video/2UczS2hQLsI/видео.html but you're correct, a Hamiltonian graph is one with a Hamiltonian cycle!
thank you
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
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! ruclips.net/video/4tu-H4ES0fk/видео.html
thanks!
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
This proof almost makes it seem obvious in reterospect.
thnx
You're very welcome!
Cool
That's for sure, love this proof! And the corollary, Dirac's Theorem! ruclips.net/video/S7bORlkfwsA/видео.html
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?