Euler's Formula and Graph Duality

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

[TheRyry]

This is the best math channel on YouTube.

[NamelessNr]

Mind blown when you put the proof together at the end.

[andy-kgfb]

I come back to this video every so often to just appreciate the beauty and motivate myself to work harder.

[silpheedTandy]

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!!

[davtor]

Beautiful. Far-and-away my favorite Math youtube channel!

[TheWolfboy]

damn randolph's legs are creepy as hell

[dylanwalker]

PLEASE THANK YOU FOR USING CHARACTERS IN THE MOVIE TRADING PLACES IN YOUR EXAMPLES. Such a pleasant surprise to break the monotony of maths.

[DoubleBob]

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.

[rosebuster]

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.

[MyAce]

You just reminded me why graph theory is so cool and beautiful; thanks for rekindling my interest in one of my favorite subjects.

[abhirupgupta]

I am appreciating yt channels like this more after getting into college. Cool Stuff!

[antonshalgachev]

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.

[aSeaofTroubles]

Wow! This makes WAY more sense than whatever I read on Wikipedia. Suddenly I'm not afraid of graph theory

[SunnyZhu-fgzb]

beautiful connection between euler's formula and the properties of spanning trees! I never thought of that

[th_wall]

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.

[Magnasium]

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

[madisonpage]

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.

[sophiacristina]

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...

[pearlclam]

This is the best channel, no subcategories, on Youtube.

[alvarol.martinez]

+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.