Edge Connectivity of Complete Graphs | Graph Theory

What is the edge connectivity of Kn, the complete graph on n vertices? In other words, what is the minimum number of edges we must delete to disconnect Kn? We'll prove this is n-1 in today's graph theory video lesson!

For K1, the trivial graph, we define its edge connectivity to be 1. For any other complete graph, any single vertex has n-1 neighbors, thus we can disconnect it by deleting the n-1 edges joining a vertex to its neighbors. This isolates the vertex, disconnecting it from the rest of the graph. It then remains only to prove that we MUST delete at least n-1 edges to disconnect Kn, that is, that it cannot be done by deleting fewer edges.

Edge Cuts and Edge Connectivity:    • Edge Cuts and Edge Connectivity | Gra...  
Vertex Connectivity of a Graph:    • Vertex Connectivity of a Graph | Conn...  
Bounds on Vertex Connectivity:    • Simple Bounds on Vertex Connectivity ...  

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