📂Graph Theory

Graph k-connectivity and Menger's Theorem

Definition

For a given graph $G$, let the number of components be denoted by $\text{comp} (G)$.

Edge-Connectivity

1. A set of edges satisfying the following conditions is called a disconnecting set of $G$. $$\text{comp} \left( G \setminus D \right) > \text{comp}(G)$$
2. A disconnecting set of $G$ that does not have a proper subset which is also a disconnecting set is called a cutset of $G$.
3. If $G$ is a connected graph, the smallest cardinality among the edge cutsets is denoted as the edge-connectivity $\lambda (G)$.
4. A cutset $\left\{ e \right\}$ that is a singleton set is called a bridge if it satisfies $e$.

Vertex-Connectivity

1. A set of vertices satisfying the following conditions is called a separating set of $G$. $$\text{comp} \left( G \setminus S \right) > \text{comp}(G)$$
2. If $G$ is a connected graph, the smallest cardinality among the separating sets is denoted as the vertex-connectivity $\kappa (G)$.
3. For all $S \subset V(G)$ such that $\left| S \right| < k$ and if $G \setminus S$ is a connected graph that is not a complete graph, it is called a $k$-connected graph.

Explanation

As an example, the vertex-connectivity of the complete graph $K_{n}$ is trivially $\kappa \left( K_{n} \right) = n-1$.

In the following figure $e_{5}$ is a bridge¹.

Disconnecting Set

A disconnecting set can be any set that increases the number of components, simply by cutting the graph. $E(G)$ is inevitably a disconnecting set, but it is too trivial to be meaningful. Here are some examples of disconnecting sets. $$\left\{ e_{5} \right\} \\ \left\{ e_{1}, e_{4} \right\} \\ \left\{ e_{1}, e_{2} , e_{3}, e_{4}, e_{5} \right\}$$

Cutset

Simply put, the smallest disconnecting set is a cutset. The reason for the complex expression “a disconnecting set that does not have a proper subset which is also a disconnecting set” is that it is not just any small disconnecting set, but is the smallest in the sense of a partially ordered set formed by taking many disconnecting sets. Thus, there is no guarantee of uniqueness for a cutset, and the cutsets in the example above are the following five. $$\left\{ e_{5} \right\} \\ \left\{ e_{1}, e_{4} \right\} \\ \left\{ e_{1}, e_{2} \right\} \\ \left\{ e_{2} , e_{3} \right\} \\ \left\{ e_{3}, e_{4} \right\}$$

Edge-Connectivity

If the graph in the figure above is $G$, the edge-connectivity $\lambda (G)$ is calculated as $\left| \left\{ e_{5} \right\} \right| =1$.

In the definition, a connected graph is a $1$-connected graph, meaning that even without removing any vertices, it is already a connected graph. A $k$-connected graph is a generalization of a connected graph. Connectivity $\kappa (G)$ is also defined as the largest number among $k$ when $G$ is a $k$-connected graph. Normally, when referring to a $k$-connected graph, it means this vertex-based $k$-connected graph. Although it is possible to define an edge-based $k$-connected graph, it is rarely mentioned in detail. However, in this post, the description is mainly focused on edges for the sake of explanation.

Theorem

Finally, we introduce the following most famous theorem concerning $k$-connected graphs.

Menger’s Theorem

Suppose a graph $G$ with at least $k+1$ vertices is given. Then (1) and (2) are equivalent.

• (1): $G$ is a $k$-connected graph.
• (2): There exist at least $k$ mutually disjoint paths connecting any two vertices $u,v$ as their endpoints.

---

• Here, disjoint paths mean those that share no vertices except for the endpoints $u,v$.