Proof: Upper Bound for the Size of Planar Graphs | Graph Theory

The size of a planar graph must be less than or equal to three times the number of vertices minus 6. That is, for a planar graph of order n, size m, and with r regions when imbedded in the plane, m is less than or equal to 3n - 6. We'll prove this upper bound for the size of planar graphs in today's graph theory lesson!

This result follows from Euler's formula for plane graphs. Links to a proof below. A maximal planar graph is a graph that, with the addition of any edges, would become nonplanar. As it turns out, a non planar graph of order n (n greater than 2) will be maximal if it has 3n-6 edges.

What are Planar Graphs:    • What are Planar Graphs? | Graph Theory  
Proof of Euler's formula for Plane Graphs:    • Proof: Euler's Formula for Plane Grap...  

◆ Donate on PayPal: https://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