Proof: Graph has a Cycle Longer than its Minimum Degree | Graph Theory

If G is a graph with minimum degree delta, with delta greater than or equal to 2, then G contains a cycle of length at least delta+1. In other words, a graph with minimum degree at least 2 must have a cycle whose length is greater than its minimum degree!
What is the degree of a graph: • What are Adjacent Vert...
Here is a similar proof regarding paths: • Proof: Every Graph Con...
Thanks to Nasser Alhouti, Robert Rennie, Barbara Sharrock, and Lyndon for their generous support on Patreon!
◆ 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: / @emery3050

[@sailikhithaandraju3800]

I think i should post this comment . I watched many playlists of discrete mathematics but yours is the BEST . You explain everything in detailed sir . A LIFE SAVIOUR.

[@PunmasterSTP]

Out of curiosity, what other playlists did you watch?

[@masseffect0128]

I'm a bit confused here Sir, At 08:16, why is k - i >= δ? If Vi is the first neighbor of V(k - 1) must be it's last neighbor, and since Vn has δ neighbors, that gives k - i = δ.

[@WrathofMath]

Thanks for watching and good question! You said Vn has δ neighbors, and it is possible I missed something in quickly skimming through the lesson - but I don't think we know precisely how many neighbors any of these vertices has. At least one of them has δ neighbors, since δ is the minimum degree, but for any vertex all we know is its degree must be AT LEAST δ.
Then, since all of the neighbors of Vk must lie between Vi and Vk-1 on our path, that number of vertices from Vi to Vk-1 has to be at least δ, to account for the at least δ neighbors. From the beginning of the path to Vk-1 is a total of k vertices, but we aren't considering the vertices from V0 to Vi-1, which is a total of i vertices we are not considering. Thus, the number of vertices from Vi to Vk-1 is k-i. This is the number that must be at least δ. So, k-i is greater than or equal to δ. Does that help at all?

[@user-qj3pt4tp7x]

thank you!

[@shaibal_saha]

Let k ≥ 3 and δ ≥ 2. Prove that if G is a simple graph such that δmin(G) ≥ δ
and every cycle of G has length at least k, then G contains a cycle of length at least
(δ − 1)(k − 2) + 2. how to approach this to prove

[@GeigerPancake16]

Great proof👌

[@WrathofMath]

Thank you! The power of a longest path is not to be underestimated!

[@untoldlove-family]

My question is "could delta value change according to the length of the cycle?" That is if I take delta= 3 then the cycle whose length 4 and minimum degree of the cycle should be 4 or not? Kindly explain

[@user-bo5gt9jv9e]

Does this assume that a longest path always exist?

[@WrathofMath]

Yes, because such a path will exist. We can consider every path in a graph, list their lengths, and take the maximum since it will always be a finite set. This longest path may not be unique, but it will exist. It may even have length 0, like in the case of the complement of a complete graph, but there will be a longest path.

[@planetero4442]

Do you have any idea about the relation between the minimum degree and planar graphs?, as an example how to show that in a planar graph, the minimum degree is less or equal to 5,
And if G is planar without a triangle, then minimum degree of G is less or equal to 3, thank you so much.

[@WrathofMath]

Thanks for watching and here is a lesson on the first of those topics: ruclips.net/video/sYOxBNyd9Ok/видео.html
I don't immediately recognize the second result, but I'll look into it and perhaps do a video on it!

[@ArmanAsadi-y5z]

Nice❤

[@WrathofMath]

Thanks!

[@PunmasterSTP]

Anyone else still watching in 2025?
And awesome, another longest-path proof! 👍