Connectivity
Graph connectivity is also known as graph resilience and is a measure of how well a graph can maintain its connectivity when vertices or edges are removed, i.e. how many vertices or edges can be removed before the graph becomes disconnected (from one connected component to multiple connected components) or has a higher number of connected components.
With this analysis technique we can find out how robust a graph is, i.e. how well it can handle failures which can be very useful in real world applications such as communication, transportation, etc.
Bridges
A Bridge is an edge that if removed would increase the number of connected components in the graph. In the graph below you can quiet clearly see that the edge between vertices and marked in red is a bridge.
Cut Vertices
The same idea as a bridge also applies to vertices. A vertex is a cut vertex if removing it would increase the number of connected components in the graph. In the graph below you can quiet clearly see that the vertices and are cut vertices. These cut vertices are very important vertices as they are brokers between different parts of the graph.
k-Connected Graphs
k-Vertex-Connected Graphs
A graph is -vertex-connected if it has at least vertices and at least vertices have to be removed to disconnect the graph.
The vertex connectivity of a graph is the largest such that is -vertex-connected. So for example the graph below has a vertex connectivity of 2, because it is 2-vertex-connected. If we remove the vertices and the graph becomes disconnected but if we only remove one vertex the graph stays connected.
k-Edge-Connected Graphs
The same idea as for vertex connectivity also applies to edge connectivity. A graph is -edge-connected if it has at least vertices and at least edges have to be removed to disconnect the graph. So the graph below is 2-edge-connected and also has an edge connectivity of 2. If we remove the edges and the graph becomes disconnected.