Every Planar Graph has a Vertex of Degree 5 or Less | Graph Theory

Every planar graph has a vertex of degree 5 or less! We'll be proving this result in today's graph theory lesson. This is a result which follows quickly from the upper bound for the size of planar graphs - which is a corollary of Euler's formula for plane graphs. Links to proofs below.

Our proof today will use the contrapositive - we'll assume a graph doesn't have a vertex of degree 5 or less - thus all of its vertices have degree at least 6. Then, using the first theorem of graph theory, we'll easily show such a graph must exceed the upper bound for the size of planar graphs - and thus is nonplanar. Hence, if a graph is planar, it must have a vertex of degree 5 or less.

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

◆ 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