📂Graph Theory

Graph k-connectivity and Menger's Theorem

Definition

Let’s denote the number of components in a given graph $G$ as $\text{comp} (G)$.

• 1-1. The set of edges $D \subset E(G)$ satisfying the following is called the Disconnecting Set of $G$. $$ \text{comp} \left( G \setminus D \right) > \text{comp}(G) $$

• 1-2. Among the disconnecting sets of $G$, the one which does not have a proper subset that is a disconnecting set is called the Cutset of $G$.

• 1-3. When $G$ is a connected graph, the smallest cardinality of (edge) cutsets is represented as the edge-connectivity $\lambda (G)$.

• 2-1. The set of vertices $S \subset E(G)$ satisfying the following is called the Separating Set of $G$. $$ \text{comp} \left( G \setminus S \right) > \text{comp}(G) $$

• 2-3. When $G$ is a connected graph, the smallest cardinality among separating sets is shown as the vertex-connectivity $\kappa (G)$.

• 3. For all $S \subset V(G)$ where $\left| S \right| < k $, if $G \setminus S$ is a connected graph, then $G \ne K_{k}$ is called a $k$-connected graph.

Explanation

1-2: Cutset $\left\{ e \right\}$, which is a singleton set, can define $e$ as a bridge. In the following figure, $e_{5}$ is a bridge.

¹

2-3: The connectivity of complete graph $K_{n}$ is obviously $\kappa \left( K_{n} \right) = n-1$.

Let’s examine the 1-n. examples using the graph in the above figure:

1-1: A disconnecting set only needs to increase the number of components, i.e., it just needs to break the graph. $E(G)$ is obviously a disconnecting set, but it’s 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\} $$

1-2: Simply put, the smallest disconnecting set is the cutset. The reason why it’s phrased as ‘among disconnecting sets, the one which does not have a non-disconnecting proper subset’ is because it’s not just the smallest disconnecting set in a straightforward sense, but smallest in the sense of the partially ordered set formed by numerous disconnecting sets. Therefore, there’s no guarantee that the cutset is unique, and in the above example, there are five kinds of cutsets. $$ \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\} $$

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

It can be understood from the definition that a connected graph is a $1$-connected graph, which is to say, a $k$-connected graph is a generalization of a connected graph when no vertices are removed. The connectivity $\kappa (G)$ is also defined as the largest number of $k$ when $G$ is a $k$-connected graph. Although $k$-connected graph generally refers to this vertex-based $k$-connected graph, the definition can also apply to edges, forming an $k$-(edge) connected graph, though it’s not often detailed. However, for the sake of explanation, this post mainly discusses edge-based aspects.

Introducing the following famous theorem about the $k$-connected graph.

Menger’s Theorem

Let’s assume that a graph $G$ with at least $k+1$ vertices is given. (1) and (2) are equivalent.

• (1): $G$ is a $k$-connected graph.
• (2): There exist at least $k$ vertex-disjoint paths having arbitrary two vertices $u,v$ as their starting and ending points, excluding $u,v$ themselves.