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: [ Ссылка ]
Proof that deleting an edge disconnects a graph iff it lies on no cycle: [ Ссылка ]
Proof that tree of order n has size n-1: [ Ссылка ]

◆ Donate on PayPal: [ Ссылка ]
◆ Support Wrath of Math on Patreon: [ Ссылка ]

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: [ Ссылка ]
● Facebook: [ Ссылка ]
● Twitter: [ Ссылка ]

My Music Channel: [ Ссылка ]

свернуть