10:26 At this point we know that there must be an edge {x,y} where x is in C and y is not in C. Doesn't this already allow us to construct a trail which is longer than C? (Start from x, go all the way around C, and finally through {x,y}.) Doesn't this already contradict the fact that C is a trail with maximum length? Thanks.
Thank you! That's a clip from my rap proving there are infinitely many primes: th-cam.com/video/3er2XfJSG_k/w-d-xo.html I've got a whole playlist of math songs: th-cam.com/play/PLztBpqftvzxW7a66b0dJPgknWsfbFQP-c.html And recently made a channel just for math raps! th-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html Suffice to say, there are a lot more bars where those came from!
I don't really get it at 9:05 when you say that just because v needs an extra edge to have an even degree and we assumed that u != v, we have u=v. Why does v needing to add that extra edge lead us to u = v? Also, where exactly is u in the blue diagrams?
Thanks for watching and great question! As for where u is in the diagram, it is where v is since they're the same, but I understand that isn't super helpful haha. The reason we can conclude u=v is that the contradiction argument we made can be made for any vertex that isn't u. So if the last vertex of the trail, v, is not u, then it must be incident with an odd number of edges on the trail (2 edges anytime the trail passes through it, and +1 edge when we arrive at it finishing the trail). Thus v must be incident with some other edge not on the trail (since its degree has to be even). This contradicts the trail being of maximum length, since we could then extend it with this other edge. The only vertex that would avoid this problem is u, so if v = u we don't have the contradiction. This is because the number of edges incident with u is +2 anytime we pass through u on the trail, and +1 for the last edge that finishes the trail, but also +1 for the first edge that began the trail at u (producing a total like 2k+2, which is even). So you can see it is only with the vertex u that we avoid having an odd number of incident edges, and thus avoid the subsequent contradiction. 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! th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Thank you, glad it was helpful! If you're looking for more graph theory, check out my playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank you so much for these videos, they're extremely helpful! I did have one question, Would just the first direction of the proof be sufficient or would the contraction proof also have to be given to prove the statement?
Thanks for watching and for your question. I'm not quite sure how to answer that, perhaps if you gave a little more detail of your confusion I'd be able to address it better, but let me try to explain a little here and see if it helps. I only watched a little of the video to see what part you were asking about, but I think I remember what is going on. Remember what H is: it is our original graph G, but without any edges from the circuit C. We deleted those so that in H we can use any edge that remains (because we're trying to identify an additional circuit we can attach to C, and so we need to avoid using any edges of C, that is why we are considering this graph H without any of C's edges). Now remember that C is also the longest trail of G, so there is no reason we would assume that our graph is connected after deleting every edge from that circuit. Does that make sense? In fact, after having completed the proof, we know that C does in fact contain every edge of G, so if we delete every edge of C, our graph is SURELY disconnected, since it has no edges at all. Does that help? I think it was a fairly unimportant remark in the proof, but I did want to point out that our graph H is not necessarily connected.
I was wondering if you could help explain a puzzle to me, and if there's any math to go along with that explanation. Basically, you draw a large rectangle, lengthwise up and down. Draw a vertical line down the middle of that rectangle. Now, on the left half of the rectangle, draw two horizontal lines to split the left side into thirds. On the right half of the rectangle, draw one horizontal line to split the right side in half. So far, what you should have drawn is a rectangle that has 3 boxes on the left and 2 boxes on the right. Next, draw a dash through every edge that intersects with other edges. All in all, there should be 16 dashes (9 on the outside of the rectangle, 7 connecting the inside boxes). And so, the point is this: each dash represents a door to a room. Go through each of the doors, do so only once, and don't lift your pencil.
Thanks for watching and for the fun puzzle! We could definitely solve that with graph theory. Just let each room (including outside) be a vertex, and let spaces that can be traveled between be joined by an edge (so edges basically represent doors). Look up some results on Eulerian paths and I think that will solve your problem. I may make a video on it sometime!
made it easy to understand, was going through West's introduction to graph theory, your video worked like charm
Thanks for watching and I am glad to hear it was easy to understand!
thank you, I needed to teach that with a proper proof and the way you presented here covers everything fully
Glad it was helpful!
10:26 At this point we know that there must be an edge {x,y} where x is in C and y is not in C. Doesn't this already allow us to construct a trail which is longer than C? (Start from x, go all the way around C, and finally through {x,y}.) Doesn't this already contradict the fact that C is a trail with maximum length? Thanks.
that was supposed, C is not maximum circuit, for contradiction
Great video! Didn't expect you to go so hard with the bars at the end 🔥🔥🔥
Thank you! That's a clip from my rap proving there are infinitely many primes: th-cam.com/video/3er2XfJSG_k/w-d-xo.html
I've got a whole playlist of math songs: th-cam.com/play/PLztBpqftvzxW7a66b0dJPgknWsfbFQP-c.html
And recently made a channel just for math raps! th-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html
Suffice to say, there are a lot more bars where those came from!
Wow this was a very beautiful video of proof can't appreciate you enough for this
Amazing, having graph theory this semester and i am behind because i was sick your ,videos helping me
Crystal clear proofs..Keep uploading videos.
Thank you, I will!
I don't really get it at 9:05 when you say that just because v needs an extra edge to have an even degree and we assumed that u != v, we have u=v. Why does v needing to add that extra edge lead us to u = v? Also, where exactly is u in the blue diagrams?
Thanks for watching and great question! As for where u is in the diagram, it is where v is since they're the same, but I understand that isn't super helpful haha. The reason we can conclude u=v is that the contradiction argument we made can be made for any vertex that isn't u. So if the last vertex of the trail, v, is not u, then it must be incident with an odd number of edges on the trail (2 edges anytime the trail passes through it, and +1 edge when we arrive at it finishing the trail). Thus v must be incident with some other edge not on the trail (since its degree has to be even). This contradicts the trail being of maximum length, since we could then extend it with this other edge.
The only vertex that would avoid this problem is u, so if v = u we don't have the contradiction. This is because the number of edges incident with u is +2 anytime we pass through u on the trail, and +1 for the last edge that finishes the trail, but also +1 for the first edge that began the trail at u (producing a total like 2k+2, which is even). So you can see it is only with the vertex u that we avoid having an odd number of incident edges, and thus avoid the subsequent contradiction. Does that help?
Eulerian iff? More like "Amazing videos, with demonstrations and diagrams that are lit!" 🔥
Thanks u so much.
Your proving style is very intuitive and interesting.
You are most welcome!
Fantastic explanation and clear graphics to help understand!
Thanks a lot! Glad it was clear!
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!
th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
My assignment is super duper easy now, thanks a lot
Glad it helped, thanks for watching!
The best proof I found on the net
Thank you, glad it was helpful! If you're looking for more graph theory, check out my playlist: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank you so much for these videos, they're extremely helpful!
I did have one question, Would just the first direction of the proof be sufficient or would the contraction proof also have to be given to prove the statement?
Finally I understand it clearly thanks for making it :-)
So glad it helped! Thanks for watching!
Thank you, loved the explanation
You're very welcome, thanks for watching!
Thank you so much!
Thank you! This was very very helpful.
You're welcome! I am glad it helped and thank you for watching!
Nice and clear, bravo!
Thanks for watching and I am glad you found it clear!
Nice explanation
Thank you, glad it was clear!
Bro you are awesome.
Thank you!
Do you have similar kind of proof for Directed Graph?
I did not understand it when you said H may not be a connected graph. Why is it so? Thank you.
Thanks for watching and for your question. I'm not quite sure how to answer that, perhaps if you gave a little more detail of your confusion I'd be able to address it better, but let me try to explain a little here and see if it helps. I only watched a little of the video to see what part you were asking about, but I think I remember what is going on.
Remember what H is: it is our original graph G, but without any edges from the circuit C. We deleted those so that in H we can use any edge that remains (because we're trying to identify an additional circuit we can attach to C, and so we need to avoid using any edges of C, that is why we are considering this graph H without any of C's edges). Now remember that C is also the longest trail of G, so there is no reason we would assume that our graph is connected after deleting every edge from that circuit. Does that make sense? In fact, after having completed the proof, we know that C does in fact contain every edge of G, so if we delete every edge of C, our graph is SURELY disconnected, since it has no edges at all. Does that help? I think it was a fairly unimportant remark in the proof, but I did want to point out that our graph H is not necessarily connected.
I was wondering if you could help explain a puzzle to me, and if there's any math to go along with that explanation.
Basically, you draw a large rectangle, lengthwise up and down. Draw a vertical line down the middle of that rectangle.
Now, on the left half of the rectangle, draw two horizontal lines to split the left side into thirds. On the right half of the rectangle, draw one horizontal line to split the right side in half.
So far, what you should have drawn is a rectangle that has 3 boxes on the left and 2 boxes on the right.
Next, draw a dash through every edge that intersects with other edges. All in all, there should be 16 dashes (9 on the outside of the rectangle, 7 connecting the inside boxes).
And so, the point is this: each dash represents a door to a room. Go through each of the doors, do so only once, and don't lift your pencil.
Thanks for watching and for the fun puzzle! We could definitely solve that with graph theory. Just let each room (including outside) be a vertex, and let spaces that can be traveled between be joined by an edge (so edges basically represent doors). Look up some results on Eulerian paths and I think that will solve your problem. I may make a video on it sometime!
Lots of love from Indian occupied Kashmir.
Thank you! Much love back from the US!
😡😡😡 not occupied
Means u want to be a part of Pakistan... 😂😂😂.
Video starts at 1:10
This is great
Thank you!
Thanks
No problem, thanks for watching!
Nice
Thank you! A classic proof!
This won't work if G has loop
Cool
Thanks for watching!
@@WrathofMath oh , I like Graph Theory !
Cool song
Nice
Thank you!