Proof: Degree Sum Condition for Connected Graphs | Connected Graphs, Nonadjacent Vertices

If every pair of nonadjacent vertices in a graph has a degree sum greater than or equal to one less than the number of vertices in the graph, then the graph is connected and has a diameter less than or equal to 2, and we will prove this theorem in today's video graph theory lesson!

This is a sufficient condition for a graph to be connected, meaning if it is true about some graph G, then G is connected, but if it is not true about some graph H, we still do not know if H is connected or not, it may or may not be. For example, a path graph on 4 vertices does not fill this condition (it has two non-adjacent end vertices, with degree sum 2, which is not greater than or equal to 4 - 1 = 3).

We will restate the theorem with a little more graph theory notation. Let G be a graph of order n. Then, if deg(u) + deg(v) is greater than or equal to n-1 for every two nonadjacent vertices u and v, then G is connected and diam(G) is less than or equal to 2.

Remember that the diameter of a graph is the greatest distance between two vertices in the graph, and the distance between two vertices in a graph is the length of the shortest path that connects them.

To prove our theorem, we will consider two adjacent vertices and two nonadjacent vertices, and we will easily be able to show that in both situations, the vertices are connected by a path of length two or less!

If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!

PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ



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

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic