CORRECTION: At 30:26 I say “minimum number of internally disjoint u-v paths”, when I meant to say the words I was underlining “maximum number of internally disjoint u-v paths”. I can’t believe I didn’t catch that error during the editing!
Oh my God. I had been stuck on this proof for 3 days now. I'm pretty sure I wouldn't have been able to come up with it on my own. Also, great video! What I like most about your style is that you don't do any bs, but at the same time say just enough that if someone's watching properly, they'd be able to understand everything. Thanks a lot!
Thanks for watching and there is no shame in being stuck, this is a tough proof! I certainly wouldn't have come up with it by myself. It took plenty of thinking of my own to make sense of certain steps of this proof, and I believe in the lesson I tried to emphasize the steps I found most tricky/subtle, it's a wonderful proof! Thanks so much for the kind words and I am really glad to hear it helped, this is one of my favorite videos I've got!
Thanks a lot, glad it helped! If you're looking for more graph theory, check out my graph theory playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
So glad to help! Thanks for watching, and check out my graph theory playlist if you're looking for more. Good luck on the final! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Question: in case 2, what if there are multiple paths from u to a single member of the disconnected set (a single w_i). The pseudo graph you drew makes it seem like there can only be one of these paths? Can’t there be more
Thanks for watching! Case 3 is tricky too, for me Case 2 was definitely the trickiest, but I suppose it's different for everyone! Regardless, it is a challenging and wonderful proof!
Thanks so much, Madalina! I'd be happy to if I think I could make a good lesson on it, but could you specify which of Mader's theorems in particular? There a few that occasionally bear his name.
Thank you so much for the video, it was quite easy to follow for such a long proof :D wanted to check that at 22:40 you say geodisc, did you mean geodesic? or is it also called a geodisc? anyways thanks a lot
You're very welcome, I am so glad it helped! I did mean geodisc! Given two vertices u and v in a graph G, a u-v geodisc is a shortest path between u and v in G. So if P is a u-v geodisc, then d(u,v) equals the length of P.
Hi I really enjoyed the video. Just for the record, however, on p.15 of "Introduction to Graph Theory" (Chartrand and Zhang), those authors refer to a as any u-v path whose length is d(u,v). Then on p.79 they say "Let P(u,x,y,...,v) be a u-v geodesic in G..." So a geodesic a shortest path between two vertices, sort of the straight lines of graph theory. Cheers
us suppose that you have Rs 40 at your disposal and you are hungry. There are four items on which you can spent your money. They are: a) a cup of coffee; b) four pieces of samosas c) a bowl of noodles; and d) a bottle of cold drink. Price of each of these items is Rs. 40. b) Which one item will you choose? If you have Rs. 80 then which two items will you choose and how do you rank them? Again, if you have Rs. 120 what will be your preferred choices? If you have Rs 200 at your disposal, do you need to economize? Give arguments foryour answer.
dude i didnt understand your conclusion of case 1 as you just reiterated the statement that k-1, u-v separating set, implies the k-1 disjoint path. Normally a proof should converge to the conclusion but you just vaguely said it, i thing you are missing something. please enlighten this noob.
CORRECTION: At 30:26 I say “minimum number of internally disjoint u-v paths”, when I meant to say the words I was underlining “maximum number of internally disjoint u-v paths”. I can’t believe I didn’t catch that error during the editing!
how can G-e and G have same number of maximum internally disjoint u-v path. it has to be 1 more than G-e for G.
Thank you so much! Clearest description of this proof anywhere on the internet.
You're very welcome! Thanks a lot for watching, I am glad you found it clear!
Proof of Menger's Theorem? More like "Perfect illustrations; thanks for including lots of them!" 👍
This is so much clearer than when it was lectured!
So glad it helped, thanks for watching!
Oh my God. I had been stuck on this proof for 3 days now. I'm pretty sure I wouldn't have been able to come up with it on my own.
Also, great video! What I like most about your style is that you don't do any bs, but at the same time say just enough that if someone's watching properly, they'd be able to understand everything. Thanks a lot!
Thanks for watching and there is no shame in being stuck, this is a tough proof! I certainly wouldn't have come up with it by myself. It took plenty of thinking of my own to make sense of certain steps of this proof, and I believe in the lesson I tried to emphasize the steps I found most tricky/subtle, it's a wonderful proof! Thanks so much for the kind words and I am really glad to hear it helped, this is one of my favorite videos I've got!
Very clear and very interesting
Great explanation! Thanks a ton!
Thanks a lot, glad it helped! If you're looking for more graph theory, check out my graph theory playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
You're my favourite math channel besides Numberphile
Thanks a lot! Numberphile is definitely one of the great math channels!
I was dreading having to go through the stale lecture notes before my GT final. You just made my evening a lot easier. Thank you !
So glad to help! Thanks for watching, and check out my graph theory playlist if you're looking for more. Good luck on the final! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath;;;;;;;;
@@WrathofMath;;;;;;;;;
@@WrathofMath;
@@WrathofMath;
Hey there! I would like to ask, if we were to prove Menger's theorem over edges, what should we change? Thank you in advance:)
Thank you so much
Heyy, can you explain the Bondy Chvatal theorem please?
Question: in case 2, what if there are multiple paths from u to a single member of the disconnected set (a single w_i). The pseudo graph you drew makes it seem like there can only be one of these paths? Can’t there be more
Thanks.. for me case 3 was more difficult than 2
Thanks for watching! Case 3 is tricky too, for me Case 2 was definitely the trickiest, but I suppose it's different for everyone! Regardless, it is a challenging and wonderful proof!
is this video cover whole theorem like mengers theorem aae 3
This is amazing! Could you do a video also about Mader's theorem?
Thanks so much, Madalina! I'd be happy to if I think I could make a good lesson on it, but could you specify which of Mader's theorems in particular? There a few that occasionally bear his name.
Wrath of Math Theorem 3.5 (Mader 1972). Every graph of average degree at least 4k has a k-connected subgraph.🤗 thank you :)
Thank you so much for the video, it was quite easy to follow for such a long proof :D
wanted to check that at 22:40 you say geodisc, did you mean geodesic? or is it also called a geodisc?
anyways thanks a lot
You're very welcome, I am so glad it helped! I did mean geodisc! Given two vertices u and v in a graph G, a u-v geodisc is a shortest path between u and v in G. So if P is a u-v geodisc, then d(u,v) equals the length of P.
Hi I really enjoyed the video. Just for the record, however, on p.15 of "Introduction to Graph Theory" (Chartrand and Zhang), those authors refer to a as any u-v path whose length is d(u,v). Then on p.79 they say "Let P(u,x,y,...,v) be a u-v geodesic in G..." So a geodesic a shortest path between two vertices, sort of the straight lines of graph theory. Cheers
Nice explanation Thanks! I have a query that when you say u-v disjoint paths, does that mean edge disjoint or vertex disjoint paths ?
Thanks for watching and good question. We mean vertex disjoint paths, which of course also means they're edge disjoint.
@@WrathofMath okay, I got it now. Thanks for replying! 🙂
us suppose that you have Rs 40 at your disposal and you are hungry. There are four
items on which you can spent your money. They are: a) a cup of coffee; b) four pieces of samosas c) a bowl of noodles; and d) a bottle of cold drink. Price of each of these items is Rs. 40.
b)
Which one item will you choose?
If you have Rs. 80 then which two items will you choose and how do you rank
them? Again, if you have Rs. 120 what will be your preferred choices?
If you have Rs 200 at your disposal, do you need to economize? Give arguments foryour answer.
dude i didnt understand your conclusion of case 1 as you just reiterated the statement that k-1, u-v separating set, implies the k-1 disjoint path. Normally a proof should converge to the conclusion but you just vaguely said it, i thing you are missing something. please enlighten this noob.