Vertex Connectivity is Less than or Equal to Minimum Degree | Graph Theory Exercises

The vertex connectivity of every graph is less than or equal to its minimum degree, this is a simple upper bound on vertex connectivity. We prove this fact, and show an example, in today's graph theory video lesson.

This inequality is true because if a graph G is disconnected, then its vertex connectivity is 0, which is also the lowest its minimum degree could possibly be, so the connectivity is less than the minimum degree. If G is connected, then pick a vertex v of minimum degree, say the minimum degree is d. Delete the d neighbors of v. This will either make the graph trivial or disconnect v from the rest of the graph. Since deleting d = min degree vertices was sufficient to do this, we have by definition that the connectivity is less than or equal to the minimum degree.

Recall that the vertex connectivity of a graph is the minimum number of vertices we can delete from the graph to disconnect it or make it trivial.

Vertex Cuts and Vertex Connectivity:    • Vertex Cuts in Graphs (and a bit on Connec...  
Vertex Connectivity:    • Vertex Connectivity of a Graph | Graph Theory  
Simple Bounds on Vertex Connectivity:    • Simple Bounds on Vertex Connectivity | Gra...  

★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits:   / wrathofmathlessons  
◆ Donate on PayPal: https://www.paypal.me/wrathofmath

Thanks to Robert Rennie and Barbara Sharrock for their generous support on Patreon!

Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: https://crayonangel.bandcamp.com/

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

My Music Channel:    / @emery3050