Proof: Euler's Formula for Plane Graphs | Graph Theory

We'll be proving Euler's theorem for connected plane graphs in today's graph theory lesson! Commonly know by the equation v-e+f=2, or in more common graph theory notation n-m+r=2, we'll prove this famous result using a minimum counterexample proof!

The result states that, for connected plane graphs with n vertices, m edges, and r regions, n-m+r=2. This means no matter how we draw a connected planar graph in the plane, as long as our drawing has no edge crossings (as in - it is a plane graph), then n-m+r=2. For our proof by minimum counterexample, we will suppose our result doesn't hold and then consider a graph of minimum size that violates the result. By deleting an edge of this graph we will be able to find a contradiction. Many more details in the full video! You could also use induction on the size of the graph for a very similar proof.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...

[yashwant]

Perfectly described in easy and simple language . All doubts cleared

[ulissemini]

Great video! your enthusiasm makes a 15m proof feel like a 1 minute cat video

[md]

Your videos help me out so much!! I have exams soon and watching your videos make the work so much easier to understand. Thank you!!

[mike_the_tutor]

This is one of my favorite proofs and you've explained it beautifully! This is your best video yet! My only suggestion is to slow down your speech just a bit in future videos.

[mariaritacorreia]

Thank you again.
I didn't get the part on the minimum size condition. If it is minimum, how can we remove one edge?

[cobrametaliks]

Hi 👋🏻
Could you make a video about Kuratowski theorem?
Thank you for your work 🙏🏻

[maxinimus]

awesome explanation and a very passionate one as well :)

[PunmasterSTP]

Euler's Formula? More like "All these proofs are fantastic; thank ya'!" 👍

[jaeholee]

Why do we remove an edge? When you use induction, aren't you supposed to go from k edges to k+1 edges?

[benjaminlannis]

Can you prove the Jordan Curve Theorem?

[yeezyeez]

Hi why do we apply induction on m edges? Why not we apply induction on n vertices?

[aispweelun]

Hi, thanks for this video. I have a question

For the contradiction proof, are we assuming that n - m + r ≠ 2 is true for graph G with a minimum edges e? If that's the case, I don't understand how the G-e graph contradicts the n - m + r ≠ 2 because m-1 edges is already less than the minimum edges e so n - m + r ≠ 2 shouldn't apply to it

[abiralkalbani]

Dr, Could you please prove this question?
Let G and H be connected graphs different from K1 and K2.Show that both factors are paths or one is a path and the other a cycle.

[Kevin-xsft]

(Copied from J)
Hi, thanks for this video. I have a question

For the contradiction proof, are we assuming that n - m + r ≠ 2 is true for graph G with a minimum edge m? If that's the case, I don't understand how the G-e graph contradicts the n - m + r ≠ 2 because m-1 edges is already less than the minimum edges e so n - m + r ≠ 2 shouldn't apply to it

[bowlineobama]

I wish you would have used, V, E, and F labels instead of n, m and r.

[TheAaditvlog.com]

Dhau ..ham aaha k bhasaa nai bujhai xi yau 🙄😁🤔