Proof: Euler's Formula for Plane Graphs

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

Рет қаралды 21,842

3 жыл бұрын

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.
What are planar graphs: • What are Planar Graphs...
Proof that deleting an edge disconnects a graph iff it lies on no cycle: • Proof: An Edge is a Br...
Proof that tree of order n has size n-1: • Proof: Tree Graph of O...
◆ Donate on PayPal: www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
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...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic

Пікірлер: 36

@555yashwant6 Жыл бұрын

Perfectly described in easy and simple language . All doubts cleared

@WrathofMath Жыл бұрын

Glad it helped!

@ulissemini5492 3 жыл бұрын

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

@WrathofMath 3 жыл бұрын

Thanks so much! That is as high praise as I can hope for, thanks for watching and let me know if you ever have any questions!

@md8978 3 жыл бұрын

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

@WrathofMath 3 жыл бұрын

You're very welcome and thanks for watching! So glad the videos help, and good luck on your exams!

@mike_the_tutor1166 3 жыл бұрын

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.

@WrathofMath 3 жыл бұрын

It is a wonderful proof! Thanks a lot and I appreciate the feedback! I always try to monitor the speed of my voice, but sometimes I no doubt lose track of it. I've got to take more time to breathe - which will naturally slow me down a bit!

@cobrametaliks490 Жыл бұрын

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

@mariaritacorreia9340 6 ай бұрын

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

@maxinimus 11 ай бұрын

awesome explanation and a very passionate one as well :)

@WrathofMath 11 ай бұрын

Thank you!

@jaeholee1092 3 жыл бұрын

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

@benjaminlannis5050 3 ай бұрын

Can you prove the Jordan Curve Theorem?

@yeezyeez6326 Жыл бұрын

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

@abiralkalbani8751 2 жыл бұрын

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.

@StrifeHale 3 жыл бұрын

Perfect, thank you very much.

@WrathofMath 3 жыл бұрын

My pleasure, thanks for watching!

@andreeduenas 3 жыл бұрын

Thank you very much!

@WrathofMath 3 жыл бұрын

My pleasure, thanks for watching!

@aispweelun 3 жыл бұрын

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

@ulissemini5492 3 жыл бұрын

because after showing that n - m + r for G equals n - m + r for G-e it contradicts n - m + r ≠ 2 basically, so long as there are cycles you can delete an edge from a cycle while leaving the formula unchanged, I like to think of applying this over and over until you get to a tree (no cycles) where we've already proven it!

@mrDustin0Channel 2 жыл бұрын

let the vars of G-e be n', m' and r' so G-e holds n'-m'+r'=2 now place the vars of G inside it n'-m'+r'=2=n-(m-1)+(r-1) and get n'-m'+r'=2=n-m+r so we did not change anything by deleting the edge regarding the formular we know the formular holds for G-e thus the formular holds for G aswell

@PunmasterSTP Ай бұрын

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

@Kevin-xs1ft 2 жыл бұрын

(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

@rameezshafat Жыл бұрын

The task at hand involves proving a statement about a cycle graph. To do this, a minimum counterexample approach is being used, wherein the smallest possible instance that does not satisfy the statement is being considered. In order to prove the statement, it is necessary to show a contradiction, in this case we show it by deleting the edge. The goal of this contradiction is to demonstrate that the statement is, in fact, true for all cycle graphs, and that the counterexample is invalid.