Proof: Euler's Formula for Plane Graphs | Graph Theory
Вставка
- Опубліковано 12 вер 2024
- 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/...
◆ 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
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: ua-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Perfectly described in easy and simple language . All doubts cleared
Glad it helped!
Great video! your enthusiasm makes a 15m proof feel like a 1 minute cat video
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!
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!!
You're very welcome and thanks for watching! So glad the videos help, and good luck on your exams!
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.
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!
Thank you again.
I didn't get the part on the minimum size condition. If it is minimum, how can we remove one edge?
Hi 👋🏻
Could you make a video about Kuratowski theorem?
Thank you for your work 🙏🏻
awesome explanation and a very passionate one as well :)
Thank you!
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
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!
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
Can you prove the Jordan Curve Theorem?
Euler's Formula? More like "All these proofs are fantastic; thank ya'!" 👍
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.
Why do we remove an edge? When you use induction, aren't you supposed to go from k edges to k+1 edges?
Hi why do we apply induction on m edges? Why not we apply induction on n vertices?
(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
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.
Perfect, thank you very much.
My pleasure, thanks for watching!
I wish you would have used , V, E, and F labels instead of n, m and r.
Thank you very much!
My pleasure, thanks for watching!
Love you from Nepal 🇵🇰
Amazing!
Thanks for watching, Vishnu!
great !!!
Thank you! If you're looking for more graph theory check out my graph theory playlist! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
#Excelent!
I love you
❤️
Dhau ..ham aaha k bhasaa nai bujhai xi yau 🙄😁🤔