Proof: Graph is Eulerian iff All Vertices have Even Degree | Euler Circuits, Graph Theory
Вставка
- Опубліковано 12 вер 2024
- A nontrivial connected graph is Eulerian if and only if every vertex of the graph has an even degree. We will be proving this classic graph theory result in today's lesson!
Remember that an Eulerian graph is a graph containing an Eulerian circuit, check out my lesson on them if you need a recap: • Eulerian Circuits and ...
An Eulerian circuit is a circuit containing every edge of a graph.
The first direction of the proof is pretty easy, we show that a Eulerian graph's vertices all have even degrees. The other direction, proving that if all vertices of a nontrivial connected graph have even degree then the graph contains an Eulerian circuit, takes a bit more work. We will use a bunch of proofs by contradiction and find that the theorem is fairly straightforward to prove, even if it does take a lot of work!
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
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!
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
thank you, I needed to teach that with a proper proof and the way you presented here covers everything fully
Glad it was helpful!
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: ua-cam.com/video/3er2XfJSG_k/v-deo.html
I've got a whole playlist of math songs: ua-cam.com/play/PLztBpqftvzxW7a66b0dJPgknWsfbFQP-c.html
And recently made a channel just for math raps! ua-cam.com/channels/Q2UBhg5nwWCL2aPC7_IpDQ.html
Suffice to say, there are a lot more bars where those came from!
Eulerian iff? More like "Amazing videos, with demonstrations and diagrams that are lit!" 🔥
Wow this was a very beautiful video of proof can't appreciate you enough for this
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?
Amazing, having graph theory this semester and i am behind because i was sick your ,videos helping me
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
Crystal clear proofs..Keep uploading videos.
Thank you, I will!
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!
Finally I understand it clearly thanks for making it :-)
So glad it helped! Thanks for watching!
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!
My assignment is super duper easy now, thanks a lot
Glad it helped, thanks for watching!
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?
Thank you so much!
Thank you! This was very very helpful.
You're welcome! I am glad it helped and thank you for watching!
Thank you, loved the explanation
You're very welcome, 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: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
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.
It’s a walk not a circuit,circuit cannot have vertices repeated but walk can have.eulerian line is a walk which covers all edges
its other way around,
circuit can have vertices repeated, but edges cannot repeat, have to start and end on same vertex.
walk can have vertices repeated, can have edges repeated, not required to start and end on same vertex.
Video starts at 1:10
This is great
Thank you!
Thanks
No problem, thanks for watching!
Cool song
This won't work if G has loop
Nice
Thank you!
Cool
Thanks for watching!
@@WrathofMath oh , I like Graph Theory !
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... 😂😂😂.
Nice
Thank you! A classic proof!