Euler's Formula and Graph Duality
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- 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
![[UNCUT] “บอสณวัฒน์” ลากไส้!! ใครหนุนหลัง "แม่ตั๊ก ป๋าเบียร์" I คนดังนั่งเคลียร์ I 30 ก.ย. 67](http://i.ytimg.com/vi/QlD7mU2KKRk/mqdefault.jpg)
This is the best math channel on TH-cam.
+Ryan Tamburrino Yes
This is the best -math- channel on TH-cam
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.)
damn randolph's legs are creepy as hell
It reminds me of the "casually approach child" image
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.
Mind blown when you put the proof together at the end.
Didn't see that coming 😀
I am appreciating yt channels like this more after getting into college. Cool Stuff!
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
Wow. In my studies (computer science) we did this proof. It took more than an hour and I was totally confused. Now I understand it after only seven and a half minutes. I guess I'm more of a "visual and brief"-guy and less of a "proof by contradiction using induction and ten different laws"-guy. I wish I could retake all my math courses, learning from a professor like you.
Honestly kinda surprised that the inductive version would take an hour. It's a pretty straightforward proof, as I recall. It nearly suffices to just say that, if you're adding an edge, you're also adding either a vertex or a face, and never both. Thus, the addition of edges retains the accuracy of the function. You want some formal bits around the edges, like the base case and a specific outlining of how each of those two inductive cases function, but that's not an overly complex thing to do.
Not to say this proof isn't great though. My favorite kinds of proofs are ones like this, where you do a few seemingly unrelated things and then the result just kinda plops out as though it were always there in plain sight. And I don't begrudge anyone for liking that kinda proof over induction, of course. But it strikes me as odd that this proof could be over-complicated that thoroughly.
Yes the proof is fairly short and only took a few mins in my class iirc.
Yeah, I remember it being rather straightforward, just made weirdly not straightforward by the lack of precise problem formulation. However, I actually came up with a really simple way to construct it while walking about. He has those two graphs, one with one more intersection than the other. If you understand the second graph as having a certain number of edges relative to the other, as opposed to an absolute quantity of edges determined by a formula, you can just imagine each graph connected to the same larger graph of arbitrary size and structure. Thus, you have a pretty normal n, n+1 thing going on, and thus the basis for the entire inductive proof.
@@eggynack I also like the Induction proof more. It is less abstract, and we are logically doing stuff to arrive at something. I am more of a rigorous proof kind of person. Visual are interesting but we need proper math to prove stuff just the same.
5 years late but I usually find that learning something for the first time is much harder than coming back to it after some time has passed and practicing it. 3B1B's explanation only aids in our understanding.
I can finally remember this formula for the first time in my life.
I come back to this video every so often to just appreciate the beauty and motivate myself to work harder.
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.
Its amazing what humans can come up with i feel like a spectator in awe
+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?
Beautiful. Far-and-away my favorite Math youtube channel!
This really helped my research on identifying null-spaces on discrete exterior calculus applied to fluids. Thanks!
Wasn't there a mistake here at 7:14?isn't it ,"the total number of edges is two LESS than the number of vertices plus the number of faces"?🤔
now u got it . good job u explained this one much better than the last there . just dont lie next time
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
Wow! This makes WAY more sense than whatever I read on Wikipedia. Suddenly I'm not afraid of graph theory
WHERE ARE THE PI CREATURES??!
That is a very easy to understand proof. But a little suggestion: next time doing graph theory, can you make the edges thicker?
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.
PLEASE THANK YOU FOR USING CHARACTERS IN THE MOVIE TRADING PLACES IN YOUR EXAMPLES. Such a pleasant surprise to break the monotony of maths.
Damn that's an elegant proof.
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.
Do more Graph Theory proofs please :). love your stuff
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
These videos are excellent. Keep up the good work :)!
You just reminded me why graph theory is so cool and beautiful; thanks for rekindling my interest in one of my favorite subjects.
Randolph and Mortimer
Good one
favorite math youtube channel :)
Can you suggest some recreational math books for this topic or other interesting topics in math?
Yes! I found this proof in the book "Proofs from the book", which I'd highly recommend to anyone.
3Blue1Brown Do you think the art of problem solving books are good?
@@3blue1brown Wow, that is a great book, I'm really enjoying it, thank you very much for the recommendation.
damn that turn in the end....awesome video and awesome presentation :)
I am astonished by this proof
i love how my computer science background literally dances with mathematics in a waltz. mathematics takes the lead and computer science follows!
Would it be possible to use the outer volume in 3 dimensions to talk about objects in 4 dimensions, in the same way you can use and outer face in 2 dimensions to talk about objects in 3 dimensions? Then, would it be possible to talk about 4 dimensions in 2 dimensions by just fattening the object twice.
I’m just commenting here to get a notification when somebody answers your question because it sounds interesting and I don’t know the answer.
The closest generalization, I think, is that it's possible to talk about the Euler characteristic on an n-dimensional surfaces (for example, planar graphs can be thought of as graphs in a sphere, which is a 2-dimensional surface). It turns out that in any graph within that surface, you have
(# vertices) - (#edges) + (#faces) - (#3D simplices) + (#4D simplices) - ...
will come out to a constant answer called the Euler characteristic (see en.wikipedia.org/wiki/Euler_characteristic#Topological_definition) of that surface. For our example, the Euler characteristic is two, so the graphs satisfy
(#vertices) - (#edges) + (#faces) = 2
I love you. Where did you study / are you studying math ?
fel IIfram I love you too. I studied math at Stanford.
3Blue1Brown I love you both... a little more.
+psilocyberspaceman I love you even more
+3Blue1Brown what sort of course would you learn this math in?
+3Blue1Brown what sort of course would you learn this math in?
Im gonna quit school and start watching every single video that you post.
A redo of your Euler's formula was well done. How about a redo of this Euler's formula?
this is awesome
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?
Of course, V-E+F is only 2 for spaces isomorphic to the sphere. You get different numbers for spaces with holes and punctures!
Who wants a playlist escence of Graph Theory?😊
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.
Do Graph theory course like you did with Linear Algebra.
you should do this video again bro the voice isnot sexy as it should be
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...
Someone get the creator some frozen orange juice concentrate!
You need to make explicit that, Mortimer's Edges + Randolf's Edges = E. Otherwise the last "putting it together" won't work
Interested persons might like to look at Imre Lakatos's Proofs and Refutations which considers Euler's Theorem exceptions, generalizations, etc.
Nice Trading Places reference!
Hello, I need a help from you.
Actually I have mathematics channel.
I like your's idea of presentation through animation.
I already have uploaded some videos via screen recording. Can you please tell me how you make such beautiful animations? Please reply ,that will help me a lot.
I think I visibly pogged when I saw the proof come together
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
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.
This was so beautiful! =)
What do you use for the animations? I would love to produce videos like these.
I actually could have used this to solve a math problem at school, but I completely forgot about this. took me 30 minutes to rederive it.
I am currently learning Geometry at my school. I feel like I am not getting taught at the level that others schools teach. Are 'proofs' and 'induction' and some of the other terms you mentioned something I should be learning? We don't learn proofs or look at proofs. We went over them a little at the beginning of the year but nobody understands them and we haven't used them since.
If you want to be a serious mathematician, then yes. I see induction at least once in all of my classes (and I’m an Electrical Engineer!). Induction isn’t too bad though. There are lots of resources on YT explaining it. For formal proofs, they are also valuable.
find the no of faces edges and vertex if ployhedron with 3 pentagonal faces meet at each vertex... can anyone help me with this problem.
Hey big fan, listen to the podcast and everything too. The graph depicted in the video with Randolph and Mortimer and implies that the red lines form a complement spanning tree that Mortimer can access and it builds to the proof. Love these video so this is no hate, but spanning trees gotta be connected. Imo would be better to show the dual of G and how its spanning tree along with Gs original spanning tree build to the Euler theorem. I was confused for a minute until I paused at 4:55 when it said textually that "the spanning tree in the original would be the COMPLEMENT of the spanning tree in the dual" Dunno why I got my wires crossed a little there....Might be me... not the video. Just my 2 cents, I'm not trying to criticize the creator.
3Blue1Brown this is one of the most brilliant things I ever watched here on TH-cam. 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
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...
Randolph & Mortimer 😃😃😃😃 Very funny and creative to take these names of Trading places movie 😄😄😄
I lake it very much 😃
This video needs a re-upload. It's a beatiful proof, that needs a fair treatment, of being high quality and of being seen by Grant's new and bigger audiance
This video was very soothing. But I don't quite grasp the concept of the duel graph. Edit: I was spelling it wrong. Its Dual graph. Now, if the original graph is the set of dots and the lines that connect them, then the dual graph is the set of faces that the original graph cuts the plane into, and the edges of the original graph that connects them.
Why does all the videos of 3b1b shift between Low brightness and high brightness even when I pause it. It looks like a problem with the mobile phone but it only happens with 3b1b videos.
i'm not very smart, and I have a question. what about a graph with one face only (like a square or triangle), we can clearly see that e-v+f=1, because there is as many vertexes than edges. where am I wrong ? can someone tell me ?thank you for your time :)
Nattrium You include the outer region.
So the generalized euler characteristic formula is v-e+f = 2-2g
Can we somehow have vertex-face-genus triality
This reminds me of Zeeman's clever and simple proof of the classification of surfaces.
If the sum is two, does that imply the graph is planar and connected? I.e., is a converse of Euler's theorem true?
what about making a video on banach-tarski paradox?
1:27 "...feel free to click the appropriate annotation and skip ahead."
oh no
So the spanning tree of a graph has no cycle per definition, yet the dual graph can have cycles and stille be a spanning tree? I’m confused 🫥
1:30 congratulations to Randolph on being the first ever living pi creature to appear in a 3blue1brown video.
who got lost in dual graph? :(
watch it again carefully and memorize the definitions if you do so, it's not really hard to understand
Please could you explain dual graphs a little better? I didn't get the vertices being edges and edges being edges fact.
Wait but why do we know that the sum of randolphs and mortimers edges are ALL of the edges of the graph?
beautiful connection between euler's formula and the properties of spanning trees! I never thought of that
Euler's characteristic equation. Polyhedron shapes.
Vertices (dimension) - Egdes (connections)+ faces (including outer region for graph) = 2. OR
Dots - lines + region = 2
D6. 8 - 12 + 6 = 2
D4. 4 - 6 + 4 = 2
Graph (no intersections - planar) duality.
Cycle - path at ending at starting vertex (path - no back tracking.
Spanning tree - touches all vertex without cycles
Dual graph - make vertices
Pi has legs! Wow! It's really fun to see pi moving around:)
How do you get "(Number of Mortimer's edge) + 1 = F"? I'm counting the number of edges, and I get Number of Mortimer's edge = 7, which is the number of faces in the planar graph. So where am I going wrong? It says that "the number of edges he gets is one more than the number of vertices of the dual graph, which are faces cut out by the original graph." Can you explain this to me also?
Wow, this is wayyyyy better than the indian dudes teaching on youtube. Thanks a lot!
Seems like adding the two equations at 7:17 counts the two sets of Edges on the left side only once. Why?
V.E.F.
I'm sorry if this sounds like harsh criticism, but I'd really like your videos to be a bit more formal: you're obviously capable of transmitting math in a beautiful and interesting way, but if people are just looking for entertainment, instead of actually learning, they could go to Numberphile's channel, for example.
Thanks for the videos.
This is a fascinating proof! I figured out the inductive one myself once but had no idea of this one. I can't help thinking of a Zen-like comment: 'Every line has two ends'! More seriously, can this proof be extended to more than 3 dimensions? The more usual proof gives zero on the right-hand side of the equation for polytopes in all even-numbered dimensions (think of Vertices - Edges = 0 in polygons), and 2 for all odd-numbered ones. I'm impressed that you've been able to detach the proof from any particular 3-D shape and consider the graph by itself.
I'm wondering what would correspond to 'objects' and 'things that connect' in 4 and higher dimensions? Or could it be done starting with just the edges and vertices and noting how these define higher-dimensional sub-shapes in 4,5,6...N dimensions in the way that here the 0-D vertices and 1-D edges define surfaces and ultimately the single 3-D shape... and remembering that the N-1 dimensional 'facets' enclose the shape (polytope with convex hull) in N dimensions.
Although intuition and visualization are not much use in more than 3 dimensions, you can perhaps get some feel for higher-D by seeing an object in N dimensions as being infinitely thin in N+1 dimensions. For instance, if extending a tetrahedron to 4-D - visualize it as an infinitely thin hyper-surface in 4-D, then add just one more vertex outside the tetrahedron in the 4-D space - and join the dots, i.e. new vertex to the existing four in the 3-D plane (well, hyper-plane).
I think the above is correct as far as it goes but please let me know if not!
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.
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.
this formula is kinda fake. i tried it and instead its double the expected value -_-
I'm kinda feeling that Faces and Vertices are basically the same thing! How's that!
That's why it's called duality. :)
So for every graph, A, there exists a dual graph, B, with the same number of components as it. So let's say that these two objects are equivalent, but unequal. To what extent could it be argued that A=-B?
What if the graph was a square
Why the formula doesn't work?
What prevents someone from making a list of numbers which hash to 1,2,3,... zeros respectively and then to use or reuse those numbers according to the zeroes demanded?
Whoa... that awkward moment when you come back to watch old 3b1b videos for fun, and you see the ancestors of the Pi Creatures are... circles. Does this mean they used to be Tau Creatures?
I was taught the induction argument, and tbh, this one is way more elegant!
I love any kind of duality, probably because I am inherently lazy. XD
I wonder if this graph duality can be translated into some sort of categorical duality?
I know what a cycle is, but I stayed for Randolph.
Who comes and dislike ? Probably those with Field's medal who never get satisfied with any understanding. Like me. :p
Is there any link with the Gibbs' rule, aka phase rule in chemistry?
E=E1+E2
That's why there's no 2E in the formula.
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.