Proof: Minimum Degree Condition for Connected Graphs | Graph Theory

Let G be a graph of order n, meaning G has n vertices. If the minimum degree of G is greater than or equal to n-1 divided by 2, then G is connected! We prove this sufficient (but not necessary) condition for a graph to be connected in today's video graph theory lesson!

To prove the result, we use this theorem: If G is a graph of order n such that for every pair of nonadjacent vertices u and v, deg u + deg v is greater than or equal to n-1, then G is connected. We prove that theorem in this lesson:



I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:

Follow Wrath of Math on...
● Instagram:
● Facebook:
● Twitter:

My Music Channel:

wrath of math,math lessons,math,education,math video,minimum degree condition,connected graph proof,connected graph condition,graph proof,minimum degree proof,