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

[@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?

[@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

[@まめまめた-y8t]

thank you!

[@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?

[@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

[@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: kzbin.info/www/bejne/qYqyqXWErslshc0 I don't immediately recognize the second result, but I'll look into it and perhaps do a video on it!

[@GeigerPancake16]

Great proof👌

[@WrathofMath]

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

[@RobWindey]

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.

[@PunmasterSTP]

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

[@ARTV-_-THECROW]

Nice❤

[@WrathofMath]

Thanks!