Vertex Cuts in Graphs (and a bit on Connectivity) | Graph Theory, Vertex-Connectivity

What is a vertex cut of a graph? And how can we use vertex cuts to describe how connected a graph is? We have discussed cut vertices and connected graphs before, but by tying them together in a way, we are able to characterize different levels of connectivity in graphs. The focus of this lesson is vertex-cuts, but we will introduce vertex-connectivity as well.

Remember that a cut vertex of a graph is a vertex that, when deleted, disconnects the graph or the component of the graph it belongs to. However, not all graphs have a cut vertex. If a graph is non-trivial, connected, and has no cut vertices, we call it non-separable. These graphs, if they are not complete graphs, can be disconnected if we delete some additional number of vertices.

For a connected graph G, and a subset U of its vertex set, if G-U is disconnected, we call U a vertex cut of G. If U is a vertex cut of minimum cardinality among all vertex cuts of G, then U is a minimum vertex cut and the cardinality of U is called the vertex-connectivity of G. It is a measure of the strength of the connectedness of a graph, telling us the graph will still be connected if less than |U| vertices are deleted, no matter what vertices they are.

A complete graph has no vertex cuts, deleting any number of vertices will just leave us with more complete graphs. We define the connectivity of a complete graph on n vertices to be n-1. Deleting n-1 vertices of a complete graph on n vertices leaves us with a trivial graph. Then, in general, the connectivity of a connected graph G is the minimum cardinality of a subset U, of the vertex set, such that G - U is either disconnected or trivial.

SOLUTION TO PRACTICE PROBLEM:

Since this graph is not complete, we know it will have a vertex cut. Additionally, we may notice the graph is vertex-transitive (basically this means we could move our vertex labels around to any other vertices in the graph and still have the same graph - the same vertex and edge set). Thus, it doesn’t matter which vertex we delete first in trying to find a vertex cut, they will all have the same effect. Suppose we delete a.

The options are more abundant now, we could delete g or b, they have the same effect. We could delete e or d, or we could delete f or c. These are the three distinct groups of vertices. Deleting g, for example, will result in a graph isomorphic to the graph we’d get if we deleted b.

Some experimentation will show we are unable to disconnect the graph without deleting at least 3 more vertices. I chose to delete d, then e, leaving a path graph with vertices f, g, b, and c behind. Then deleting g or b, the two vertices that aren’t end vertices, will disconnect the graph. So all in all we had to delete 4 vertices, and this is the minimum number of vertices we could have disconnected the graph with, which experimentation will show.

Other options could lead you to a cycle after deleting 3 vertices, so you’d have to delete another two, which would describe a vertex cut of cardinality 5, not a minimum vertex cut! Since the minimum cardinality of a vertex cut of this graph is 4, we say the connectivity of the graph is 4.

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