Euler's Formula and Graph Duality
HTML-код
- Опубликовано: 19 июн 2015
- A description of planar graph duality, and how it can be applied in a particularly elegant proof of Euler's Characteristic Formula.
Music: Wyoming 307 by Time For Three
Thanks to these viewers for their contributions to translations
Marathi: realcalal
This is the best math channel on RUclips.
+Ryan Tamburrino Yes
This is the best -math- channel on RUclips
Do you think it's even better than Numberphile?
yes, it is better than Numberphile, because each of the videos on this channel blew my mind to a certain point.
You can even learn stuff like linear algebra on here to! (although you have to look up how to do some stuff when he says it's unimportant to the intuition and whatever.)
Mind blown when you put the proof together at the end.
Didn't see that coming 😀
I come back to this video every so often to just appreciate the beauty and motivate myself to work harder.
Beautiful. Far-and-away my favorite Math youtube channel!
more feedback: 1) the level of background music in this video is perfect for me. present but not distracting. 2) when talking about paths, the yellow is a little too light on my monitor to make it stand out, especially compared to the white lines. maybe it's because the lines are so thin. 3) when having more than one character, it's really nice to have both male and female names; very practically it helps mentally keep track of who is who, and socially it does a little bit extra to be more welcoming/acknowledging of women in mathematics. and 4) as always, i look forward to your other videos!!
+silpheedTandy Thanks! Really great feedback.
Maybe gender neutral names, but please don't use female names at all or you'll end up with some crazy bullshit in your comments (e.g. "The male graph-spanning-tree imposes himself on the female dual-graph-spanning-tree and forces her to take a certain path. This is a clear sign of patriarchical oppression in academia!")
+FernestHall Stop opreshum me.
Oh man, the worst part is that you're right. DX I mean, that people would say stuff like that.
I think it was a play off of rick and morty
damn randolph's legs are creepy as hell
It reminds me of the "casually approach child" image
PLEASE THANK YOU FOR USING CHARACTERS IN THE MOVIE TRADING PLACES IN YOUR EXAMPLES. Such a pleasant surprise to break the monotony of maths.
You just reminded me why graph theory is so cool and beautiful; thanks for rekindling my interest in one of my favorite subjects.
Ahh, now that I've finished my math degree youtube is recommending these old but gold 3b1b videos, some that I've even seen before but went way over my head at the time (I bet I will be saying that again eventually), and some that I needed just now as I continue my journey beyond the halls. Thank you, again and again.
That's a neat proof actually. I remember a different one that was quite intuitive that I found in some book, but I don't remember the details anymore. They were treating the graph as some sort of a field, growing rice or something, surrounded with water and the edges were preventing the water from pouring inside and if I remember well the goal was to destroy several of these walls to flood all of these fields and water the rice while staying connected in such way the farmer could still walk along the remaining walls to reach everywhere. So I guess basically they were also making a tree that way. And the water that was filling the sectors as the walls were being taken down was something similar to Mortimer from this video. Traveling in the dual graph is like water pouring into each region. So in the end it was most likely more or less the same proof, just visualized like that, but I can't remember everything exactly now.
Beautiful. I have pondered this proof for several times since I learnt it as a student. Even after a course on graph theory, I did not realise it. Even if I was told to use dual graphs, I would not realise it. Thank you for this
Awesome visualization and proof, thank you :)
Having come across your video, I remembered another proof, which appeared intuitive to me those days. The idea of it was to modify arbitrary graph to a single vertex by removing vertices and edges so that V-E+F does not change. And such resulting graph would obviously have V-E+F equal to 2.
Wow! This makes WAY more sense than whatever I read on Wikipedia. Suddenly I'm not afraid of graph theory
I never saw before the difference between the quality of your old videos to the new ones, they are very good, but its amazing how you progressed...
This is the best channel, no subcategories, on RUclips.
Beautiful elegant proof, beautifully and elegantly presented!
The elegance and beauty of math at its finest. Thank you, you made my day
These videos are excellent. Keep up the good work :)!
I'm in eighth grade and I'm preparing for next year (to do AP exams). We learnt this formula, but the teacher couldn't explain it. Me being very theoretical, I did a long search to find an explanation, however, I only found examples. Thank you for clarifying this.
keep up the great work! and good luck on those exams, but i bet youll do just fine without luck
Completly mesmerized. Thank you sir!
Please don't ever stop making these superb videos
I'm one of the people that was totally fine with the original proof of this, as the original seemed to make logical and intuitive sense, but yeah, this one is super elegant. Great proofs have this quality where the connection at the end feels like it just naturally slides out of the steps preceding it, totally friction-less in form. This was definitely one of those. I had absolutely no idea where you were going with the part about dual graphs, and then it all made perfect sense in this one amazing moment. Your videos are great, is the point.
Im gonna quit school and start watching every single video that you post.
Undergrad here, trying not to get lost in my Operations Research course. This video and the linear algebra ones are helping me understand the subtleties in the various simplex and network algorithms. Thancc, gotta spread the love
This really helped my research on identifying null-spaces on discrete exterior calculus applied to fluids. Thanks!
I am astonished by this proof
Amazing presentation of this excellent proof!
5:10 Randolph and Mortimer adventures, Mortimer. A hundred years *burp* Randolph and Mortimer!
Check out the movie Trading Places with Addie Murphy and Dan Aykroyd.
Great presentation and excellent explanation. This is a great example of astute teaching. Also, the material is interesting and it makes great sense. I needed just this to help some of my Olympiad Math students (Momentum Learning Academy near Houston, TX) understand this theorem by "Oiler". =)
+3Blue1Brown First, thank you, your videos have a quality and elegance that are almost impossible to find on youtube. For instance, I watched your "Crash Course on e^x" a number of times (if only they showed that approach at my uni), and I think "What does it feel to invent math?" is beautifully encouraging. I really hope you continue to make videos like these.
I had watched this video before, but today I revisited it and started playing with dual graphs and I have learnt that they are not unique in general, since they depend on the embedding of the graph, which may not be unique. This means that the assertion "original graph Dual of dual graph" is not true in general. For example, the dual of the dual of a tree is easily dependent on the embedding of the dual. I proved that if it is 3-connected (implying a number of nice things among which I used that its dual is unique), then the dual of its dual is indeed the original. Now, some questions come to my mind:
Is it always possible to find an embedding of the dual such that the dual of the dual is the original?
Is it possible to find a sequence (original, dual(original), dual(dual(original)),...) such that the period is different than 1 or 2? It certainly cannot be different each time since the number of edges is constant and the number of graphs with k edges is finite. And the most general question,
What conditions are necessary and sufficient for the dual of the dual graph to be unique and equal to the original?
Anyway, rather than correcting one second of your video, I wanted to show that your videos are very inspiring, so please keep it up.
+Álvaro L. Martínez Sounds VERY interesting. I would love to read that, could you send me a link?
Very nice proof and animation . Explained very nicely.
Man, plz. Never stop making videos.
1:31 Here we see the first member of the beloved 3b1b Pi creature species, a blue specimin named Randolph, a likely ancestor of the now popular Randy descendant
Do more Graph Theory proofs please :). love your stuff
OMG !! Who are you. All of this is awesome. Expecting some more videos from you.
This spanning tree explanation is good. As for myself, I reasoned Euler's Characteristic Formula by looking at a tetrahedron, and then considering what would happen if an edge got a new vertex inside (it would be accompanied by the original edge splitting into 2 edges, and then there being a new pair of edges within each of the 2 face adjacent to the original edge and those 2 faces splitting into a pair of face), or if a new edge was inscribed in a face (the face would split into a pair of faces) , or if a face got a new vertex inside (it would be accompanied by a new set of edges with the number being the face rank (M), and the original face being split up into a new set of faces with the number also being the face rank), with the net result being the formula.
Awesome proof! Love it
I came home from spain. And there was a new 3Blue1Brown video. Best day ever.
This video is a literal embodiment of the Pierre Deligne quote used in the "Essence of Linear Algebra" series: "I have learned to not take pride in the difficulty of a proof. Difficulty means we have not understood. The point is to paint a landscape such that the proof is obvious."
Sure the inductive proof works, and is beautiful in its own way when considering the algebra of planar graphs. However, it lacks the unifying power of this proof, which uses most of the core concepts in graph theory, much like Euler's identity and group theory.
Thank you for the most BEAUTIFUL video c:
Awesome ❤, impressive how video making went from this to what we see today, very very very interesting video❤
Great material! Good job!
This was so beautiful! =)
That was fantastic!
Great stuff. Thanks for the video
I DEFINITELY LOVED THIS...
Somehow every one of your videos is mind blowing
damn that turn in the end....awesome video and awesome presentation :)
fabulous video! thank you!!
That's really cool! Thanks a lot
AMAZING! A non inductive proof of on of the most stunning equations in math
One day, I will have watched and completely understood all your videos. 🤗
I would really love to see you do a video about the duality of points and lines.
I believe that I am a little bit dumb since I understood this video after I watched it twice. However, it does not prevent me from commending this video! Awesome! This is much easier to understand than my Math class! Thank you.
A good example of how it is and always will be for calculations without wondering why it should be by practical experience.
favorite math youtube channel :)
I can finally remember this formula for the first time in my life.
Beautiful.
This is like magic... Thanks for sharing:-)
Great video!
I love Mathematics but I am not very good at it. I adore the way you made this so easy to understand.
Best video on graph theory.
This is great!
really like your videos, keep it up! :)
Incredible explanation
This is awesome! I just have one question, how do we know that between Randolph and Mortimer's spanning trees, all the edges will be included? Is it possible that a graph exists in which that isn't the case?
3Blue1Brown this is one of the most brilliant things I ever watched here on RUclips. Continue to do this! Do you intent to give entire lectures in some branches of math like you did for elementary linear algebra?
Yes, he currently works on an calculus series
Beautiful
this is awesome
Its amazing what humans can come up with i feel like a spectator in awe
That is a very easy to understand proof. But a little suggestion: next time doing graph theory, can you make the edges thicker?
Randy has grown up so much since this!
To check whether a Truss/frame has equilibrium or not there is formula 2j_n=3,where j stands for joints(vertices), n stands for number of members (connecting two vertices ). If the equation is satisfied by the Truss or frame one can solve using Graphic analysis without performing rigorous calculations to fine member forces.
Didn't ever think it could be so significant
now u got it . good job u explained this one much better than the last there . just dont lie next time
Thank you for letting me see this after getting very frustrated with the induction proof, which didn't actually say anything about the "nature" of the problem...
Y NO PEOPLE SUBSCRIBE TO U?
Seriously, your videos are _amazing_!
amazing. thank you.
Randolph and Mortimer
Good one
very fantastic
That is really nice
Damn that's an elegant proof.
Holy shit this is amazing!
Lovely proof.
thanks man.. that was really awsm
Interested persons might like to look at Imre Lakatos's Proofs and Refutations which considers Euler's Theorem exceptions, generalizations, etc.
Thank you very much.
A nice explanation that I think everyone can consume it
Astonishing proof
A redo of your Euler's formula was well done. How about a redo of this Euler's formula?
Do you have any formal sources you used specifically? I am writing a paper on Euler's Characteristic Formula for a final project and really enjoyed this approach.
Thank you sir... it's more effective
Best "Trading Places" reference ever :p
You are doing amazing work! Would you at some point make a video of Zeeman's proof of the classification of surfaces? (Andy Putman has a nice note on it)
Yup gonna have to watch this at least two more times to understand
you can allow edges to cross with at most 2 edges meeting at a crossing and you get v-e-x+f=2 where the x is the number of these crossings
I had to watch it twice to actually understand it, got a little confused at first with the Dual Graph. It's a pretty cool proof, I have to say.
cool proof!
This reminds me of Zeeman's clever and simple proof of the classification of surfaces.
Question: I think that if a graph has a dot that is connected to only one other dot then Euler's formula still holds, but the dual graph would have a connection from a face to it self, which I guess is not allowed as it would be an edge that starts and ends in the same dot. Are we not missing to mention the restriction that every dot has to be connected to at least two dots?
Thank you again for all these incredibly interesting videos.