Eulerian Circuits and Eulerian Graphs | Graph Theory
HTML-код
- Опубликовано: 12 сен 2024
- What are Eulerian graphs and Eulerian circuits? Euler graphs and Euler circuits go hand in hand, and are very interesting. We’ll be defining Euler circuits first in today’s lesson, as well as showing an example of why these circuits might be interesting to begin with, then we go into Euler graphs, and discuss how to describe an Euler circuit and how to know if a graph is an Eulerian graph!
An Eulerian circuit in a graph G is a circuit that visits every edge of G. Remember that a circuit is a closed walk that repeats no edges. A graph doesn’t have to be connected to have an Eulerian circuit, since it could have a disconnected but isolated vertex, which has no edges incident to it that need to be traversed by an Eulerian circuit. However, for a graph to have an Eulerian circuit, one necessary condition is that it has exactly one non-trivial component. So, any disconnected graph with an Euler circuit is only disconnected because it has some trivial components. Since that isn’t very interesting we usually just discuss connected graphs when talking about Eulerian circuits.
The good thing is that if you understand what an Eulerian circuit is, you understand Eulerian graphs! A connected graph is Eulerian if it contains an Eulerian circuit. What we find in the video lesson is that our Eulerian graph has vertices all of even degree. Interestingly, a connected graph is Eulerian if and only if all of its vertices have even degrees. So if all of a connected graph’s vertices have even degrees, then it has an Eulerian circuit, and if a connected graph has an Eulerian circuit, then all of its vertices have even degrees! This is very fascinating, and I encourage you to try to prove it on your own! Let me know if you’d like to see me go over a proof in another lesson!
The graph I use in this lesson is straight out of the textbook that introduced me to Graph Theory, “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing, and helps me continue to work on Wrath of Math!
PURCHASE "A First Course in Graph Theory": amzn.to/31hgvvJ
Eulerian circuits are also sometimes called Euler tours and Euler cycles.
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcam...
Vallow Spotify: open.spotify.c...
Vallow SoundCloud: / benwatts-3
********************************************************************
+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
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
This channel is underrated.
Best Eulerian explanatory video!
Thank you!
@@WrathofMath :D take care!
I'm hearing Graph Theory in Germany so I'm no native english speaker, but your videos are sooo great for everybody! since you talk slow and keep on repeating the most important stuff, it helps alot! thanks for your effort, super gratefull. If i pass the exam , it's only because of you!!
Thanks so much for the kind words, Anna! I do my best to make each point as clear as possible, and I have tremendous respect for you being able to learn math in a second language - that's amazing! But when you pass your exam - it's all you! I'm glad my lessons can help you understand the material, but it's you who will put your knowledge to use on the test! Good luck!
I learnt real analysis and now I am banking on you for Graph theory. Your explanations are clear, crisp and concise. Sheer clarity!
You're truly lifesaver man! I appreciate all your efforts. God bless you!
It's my pleasure, Bijay! Thanks for watching and I am glad to help!
Your explanation is so perfect for me , super easy to follow , no wasted time , good examples, I can't thank you enough , you make this so much more enjoyable and simple to study.
That means a lot, thanks so much and I am glad you found it helpful!
You are the freak'n man.
Your explanations are phenomenal and you're literally putting 99% of the videos on this topic to shame.
Thank you!
Thanks so much Michael, I'm very glad you've found my lessons helpful! I look forward to making even more graph theory videos, let me know if you have any requests!
This channel never disappoints me.
Really good
Thanks so much likith! Let me know if you ever have any requests!
love from Indian ur videos are very much helpful and your explanation is the best and understandable thank you so much for this neat explanation ❤❤❤
Your videos are so helpful. Thank you 🌸
You’re welcome and thank you for watching! I am glad you’re finding them helpful, and let me know if you ever have any video requests!
@@WrathofMath If you could do some videos on Lattice Theory, that would be super helpful 😄
I'd love to but I'm not well-read in Lattice Theory! I'll definitely put it on my list of future studies though. Currently I am primarily studying financial mathematics and graph theory, but I will start on something new next year. I look forward to bringing all sorts of new lessons on new topics over the years, and hopefully I can bring you some Lattice Theory before the sun dies!
thankyou so much!! great video..Requesting you to make a video on the theorems in euler graphs
You're very welcome and thank you! Do you mean this theorem? ruclips.net/video/wC99T3aVDKQ/видео.html
Did you have some other theorems in mind as well?
@@WrathofMath Sir, not this video..
1. Proof where the k edge disjoint subgraphs exist in 2k odd vertices, and they contain all edges of g and each is unicursal
2. Proof where an euler graph is decomposed into circuits
3. Arbitrarily traceable graphs
4. Proof of (n-1)/2 edge disjoint Hamiltonian circuits, if n>=3
Also it would be great if you could add videos of solving graph theory problems.
Your explanation best and easly understandable tankyou !!
thank you very much. from Sri Lanka
My pleasure, thanks for watching! Check out my graph theory playlist for more! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thank you very much!😍
Glad to help, thanks for watching!
makes me so sad to see such a nice channel with so less views.Hope you grow exponentially.
Believe me it makes me sad too! Thank you, I do believe Wrath of Math will grow faster and faster as long as I keep uploading quality lessons, but it takes some time for them to start getting traffic. Thanks for your support!
@@WrathofMath try stepping in front of the camera with a blackboard . Trust me it does magic.
Funny you should mention that! I've been thinking about doing that, but I need to relocate first so I can set up a good place to record that type of video. I think the lessons recorded on a screen look the best, but I definitely will do some videos in front of the camera on a blackboard or whiteboard in the future as well! I look forward to it!
@@WrathofMath Do you take one time donations anywhere?
I appreciate your asking, I do on PayPal: www.paypal.com/paypalme/wrathofmath
Any donations are very appreciated to help me keep making the best math videos I can! Let me know if you ever have any video requests!
wow a very great explanation!!!!!! i also would like to see the proof
Thank you for the video! Yes, I would like to see more on this please. Also can an Euilerian circuit contain finite number of graphs?
Thank you for watching! I'll definitely do some more lessons related to Eulerian graphs, do you have any specific requests? I'm sorry I do not quite understand your question, could you try rephrasing it?
@@WrathofMath thank you so much for your reply. One of the things that I've not had a lot of clarity on, regarding graphs and a circuit is sub graph. Let me explain using sets. Let's say we have a set of n items, that set can have a finite number of subsets. Like wise can an Eulerian circuit have a finite number graphs/subgraphs based on the number of vertices present? Does this make more sense?
I think I'm getting a little closer to understanding your question but I'm still not positive. But let me try to provide some clarity. A set of n items certainly has a finite number of subsets. It has 2^n subsets to be exact. An Eulerian circuit, if we describe it as a sequence of vertices, has no subgraphs, because it is not a graph itself, in the same way that the number 3 has no subgraphs, because it isn't a graph, it cannot have a subgraph.
However, we could take the vertices and edges in an Eulerian circuit as a graph, instead of just a sequence of vertices. This graph must also have a finite number of subgraphs, so long as it is a finite graph itself.
If we know the number of vertices present in this graph and it is a simple graph, we could definitely put an upper bound on the number of subgraphs it has with a bit of thought. For example, if a graph has 4 vertices, then it can have a maximum of (4 choose 2) 6 edges. Then, the vertex set 2^4 total subsets, and the edge set has 2^6 total subsets. Then, if we want a vertex and an edge set, there are 2^4 * 2^6 unique ways we could do that. However, not every combination of vertex and edge sets will make a subgraph. For example, we could select the empty vertex set, and an edge set with 4 edges. That is not a valid subgraph. So 2^4 * 2^6 = 1024 is certainly an upper bound on the number of subgraphs of a graph with 4 vertices.
Does that help?
@@WrathofMath thank you so much! The clarity that you offered has added to my understanding of these graphs. I really appreciate your detailed explanation!!! :) Thank you!!!
You're very welcome and I am glad it was helpful! Thanks again for watching :)
Whoo this made sense!!!
Glad to hear it, thanks for watching!
Thank you very much sir this video is really helpful
Glad to hear it, thanks for watching and let me know if you ever have any requests!
Are the vertiseys or whatever always ordered right to left and top to bottom?
Eulerian? More like "We're learning it!" 👍
ty sir...love from india maharashtra
Thank you for watching, Chetan! Much love back from New Hampshire, USA!
Thanks for the videos. I got an exam in about an hour. So yay😭
My pleasure, hope it went well!
Which complete graphs Kn have closed Eulerian trails ? Or open ?
I love ur videos! Thanks!
No problem, glad they have been helpful! If you haven't already, be sure to check out my Graph Theory playlist: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Many more lessons are coming!
@@WrathofMath i definitely will! I've already watched some from the series and I have to say graph theory is quite interesting
Can you explain these graphs but with disconnected graphs?
I love your content!
Thank you! Let me know if you ever have any video requests!
Thank you very much.🙏🙏🙏
My pleasure, thanks for watching! Check out my Graph Theory playlist for more, and let me know if you ever have any requests!
ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
@@WrathofMath sure Thanks again🙏
Good morning sir, I have a question, i hope you help me,
Does a complete graph of order 5 contains both eulerian circuit and eulerian trail? Or only eulerian circuit?
Good morning! Well, a circuit is a closed trail, so certainly if K5 contains an Eulerian circuit then it also contains an Eulerian trail. But does K5 contain an Eulerian circuit? Are you familiar with Euler's circuit theorem? Here is a proof of it, and this theorem answers our question: ruclips.net/video/wC99T3aVDKQ/видео.html
@@WrathofMath I am confused in some basic terminology. Is an Euler line same as an euler trail?
@@WrathofMath Also, how can an Eulerian line be a Hamiltonian Circuit??
Thank you
It's a great video, but in Eulerian graph, you can have two vertices with odd degrees.
thank you so much , Nice Content !!!
i request you to make video on unicursal line and graph asap , i have exam in 10 days it wil be very useful.
Do consider my request
You're welcome and thank you for watching! You got it, a lesson on unicursal graphs and unicursal lines will be out Friday, I just finished recording it! Thanks for the request!
Here the lesson is in case you missed it! ruclips.net/video/qushD7bGThg/видео.html
Love math nerds 🙌🏻🙌🏻
I’m the 6 cubed person who liked this videos
Oh, duh it’s labels the way the path goes lol
Thanks for watching! And yeah haha, when we have yet to label our vertices, we'll label them in the most convenient way, which is often in the order of some path or cycle or other structure. Once we label them, what happens - happens! Let me know if you have any other questions, and if you're looking for more graph theory, check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH