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...
Proof of Euler's formula: • Proof: Euler's Formula...
Upper Bound for Size of Planar Graphs: • Proof: Upper Bound for...
◆ 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

[@WrathofMath]

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! kzbin.info/door/yEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: kzbin.info/aero/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L

[@shinelee4]

thank you so much for your videos! I want to kindly request a video on how to easily find (and draw) K33 or K5 configuration in the nonplanar graphs ! :) hope you have a good day!

[@teqnify63]

Dude that shirt is absolute fire

[@PunmasterSTP]

Initially I thought the way to prove this would be with contradiction, but I see how nicely contraposition works out here!

[@shizheli5344]

literally the best math videos on youtude

[@WrathofMath]

Thanks so much, Shizhe - I do my best! Let me know if you ever have any questions!

[@learnhome9659]

Great lesson, Can we prove the same using Contrdiction

[@gade28934]

It's easy to understand! Thx so much!

[@WrathofMath]

No problem, glad to help! Thanks for watching and let me know if you ever have any questions. Check out my graph theory playlist if you haven't! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@gade28934]

@@WrathofMath Thx a lot !

[@juancarlosgarciaaltamirano1305]

Hello my friend, I need cite this result. Which article is the correct? Thank you.

[@athenkosimagada]

Answered my question, thank you🙏🙏

[@WrathofMath]

You're welcome, I am glad it helped and thanks for watching!

[@VinodKumar-ye7ii]

Great video.

[@WrathofMath]

Thank you! Check out my graph theory playlist if you're looking for more! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Let me know if you ever have any video requests!

[@joaovictorferreira3950]

Does this just only prove that you cannot have a graph with delta>=6; but at the same time, don't prove that a graph must have a vertex of degree 5 or less. I mean, the same logic could be used to prove that you can't have a graph with delta>=7 but this dont prove that you can have a planar graph with minimun degree of 6

[@LearningCS-jp4cb]

this is exactly what i want to ask too, @WrathOfMath can you shed some light on this? We just said graph cannot have minimum degree >=6, nowhere its said 6 is least minimum degree from which graphs become non-planar.

[@karthiksiruvalam169]

suppose , i will draw a regular hexagon and a vertex in the middle and join all the vertices to the middle one , now i have a vertex with degree 6, and planar .. can u please explain this ?

[@WrathofMath]

Thanks for watching and for your question! We have to be careful to make sure we understand the result correctly. We haven't proved that all vertices of any planar graph have degree five or less - that is not true, as your example shows. We proved that every planar graph HAS a vertex of degree 5 or less. In the example you gave, every vertex has degree 5 or less except for the one in the middle. Does that help?

[@karthiksiruvalam169]

thanks dude ❤️

[@light.236]

But there still some cases in which some vertices have degree greater than 5 and some have less than 5

[@WrathofMath]

Thanks for watching and indeed, every planar graph has a vertex of degree 5 or less, but there is nothing stopping them from having other vertices with a degree greater than 5. Consider a star graph with one center vertex that is adjacent to 100 other vertices!

[@jayanthikamaraj7295]

Sir,Can u draw a graph for the degree of vertices is 5...

[@WrathofMath]

Thanks for watching and I am not sure what your question is. Are you asking for a graph whose vertices all have degree 5? A complete graph on 6 vertices fits that condition.

[@jayanthikamaraj7295]

@@WrathofMath thanks for ur reply sir.

[@anujnarode3315]

how to prove this result for if G has k connected components?

[@WrathofMath]

Thanks for watching and if G is planar, then this result applies to each of G's components, so in fact such a graph would have at least k vertices of degree 5 or less.

[@anujnarode3315]

@@WrathofMath Thanks a lot.

[@andrewnolan5958]

Legend

[@WrathofMath]

Thanks for watching!

[@chelseafener1064]

Sean baba kral video

[@jahzeelreid5572]

draw it!!!!!!!!