Proof: Every Graph Contains Minimum Degree Length Path | Graph Theory

Every graph contains a path whose length is equal to its minimum degree. We'll prove this basic result about graphs and the paths they contain in today's graph theory lesson.

Let G be a graph with minimum degree delta. We consider a longest path P = (v_0, v_1, ..., v_{k-1}, v_k). We know v_k has at least delta neighbors, and those delta neighbors must be among the preceding vertices on the path, otherwise the path could be extended - contradicting its defining property as a longest path. The vertices on P, other than v_k, are v_0, v_1, ..., through v_{k-1}. This is a total of k vertices. Since the delta neighbors of v_k lie among these k vertices, we know k is greater than or equal to delta. Notice the length of P is k, so P has length greater than or equal to delta. If P has length delta then we are done, otherwise P is longer than delta and we can take a subpath of P with length delta.

What is the degree of a vertex?    • What is the Degree of a Vertex? | Gra...  

Thanks to Nasser Alhouti, Robert Rennie, Barbara Sharrock, and Lyndon for their generous support on Patreon!

◆ 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:    / @emery3050