Chapter 4 - Connectivity

Summary

k-connected graphs

We have already introduced the concept of a graph being connected, now we shall introduce some measure of this connectedness. The vertex connectivity, or simply connectivity k(G), of a graph is defined to be the minimum number of vertices whose removal disconnects the graph, or reduces it to a single vertex; for example k(K_P) = p - 1, k(K_n,n) = n and k(T) = 1 for any non-trivial tree T. A set of vertices which disconnects the graph in this way is called a vertex cut. If a vertex cut consists of only one vertex then that vertex is called a cut vertex. It is clear that there is always a vertex cut of cardinality at most δ(G) for any graph, giving an upper bound for the connectivity. If k(G) ≥ k then we say that G is k-connected. To illustrate these concepts, we give the following simple result.

Proposition 4.1.1The n-cube Q_n has connectivity n, and furthermore, any minimum vertex cut consists of a vertex neighbourhood.

Proof. The proof is by induction on n. The cases n = 1 and 2 are trivial.

Let n ≥ 3. Since Q_n+1 = Q_n × K₂ it may be partitioned into two copies of Q_n, G₁ and G₂, so that each vertex of G₁ has precisely one neighbour in G₂.