Vertex and Edge Cutsets

Defining how connected a graph is, is sometimes difficult. We will now define connectivity of a graph in terms of what are called vertex cutsets and edge cutsets.

Vertex Cutsets

Definition: For a connected graph $G = (V(G), E(G))$, a Vertex Cutset is a subset $W$ of the vertex set $W \subseteq V(G)$ if and only if the removal of $W$, $V(G) \backslash W = \{ x \in V(G) : x \notin W \}$ disconnects $G$.

For example, let's look at the following graph:

Screen%20Shot%202014-03-29%20at%2011.47.17%20PM.png

The vertex set of the graph above, let's call it $G$, is: $V(G) = \{ a, b, c, d, e, f, g, h \}$. Let's let $W$ be a vertex cutset, say $W = \{ e, f \}$. Hence it follows that $V(G) \backslash W = \{ a, b, c, d, g, h \}$, which results in the following graph:

Screen%20Shot%202014-03-29%20at%2011.47.40%20PM.png

Hence, $W$ is indeed a vertex cutset of $G$ since the resulting graph is disconnected.

Vertex Connectivity

Definition: For a graph $G = (V(G), E(G))$, if $W$ is a vertex cutset, such that $V(G) \backslash W = \{ x \in V(G) : x \notin W \}$, and $U$ is a vertex cutset such that $V(G) \backslash U = \{ x \in V(G) : x \notin U \}$, and $\mid X \mid ≤ \mid U \mid$ for all other vertex cutsets $U$, then the Vertex Connectivity of $G$ denoted $\kappa (G)$ is the least number of vertices whose removal disconnects $G$, that is $\kappa (G) = \mid W \mid$. If $G$ is a complete graph, that is $G = K_n$ then $\kappa (G) = \kappa (K_n) = n - 1$.

Essentially, $\kappa (G)$ is the size of the smallest cutset of a graph $G$. In the example from earlier for $W = \{ e, f \}$, $\mid \: W \: \mid = 2$. However, $\kappa (G) \neq 2$, since there exists another vertex cutset that is smaller than $W$. In fact, if $U = \{ g \}$, then $V(G) \backslash U$ disconnected the graph, so in fact, $U$ is the smallest vertex cutset that disconnects the graph $G$, and hence, $\kappa (G) = 1$.

Edge Cutsets

Definition: For a connected graph $G = (V(G), E(G))$, an Edge Cutset is a subset $M$ of the edge set $M \subseteq E(G)$ if and only if the removal of $M$, $E(G) \backslash M = \{ \{x , y \} \in E(G) : \{ x, y \} \notin M \}$ disconnects $G$.

Essentially, edge cutsets are the same thing as vertex cutsets with relevance only to edges. For example, in the following graph:

Screen%20Shot%202014-03-30%20at%2012.29.52%20AM.png

The edge set of the following graph, let's call it $G$, is $E(G) = \{ \{a, b \}, \{b, c \}, \{b, d \}, \{c, d \}, \{c, e \}, \{d, e\}, \{d, f \}, \{e, f \} \}$. Suppose that $M = \{\{d, f \}, \{e, f \} \}$ Then $E(G) \backslash M = \{ \{a, b \}, \{b, c \}, \{b, d \}, \{c, d \}, \{c, e \}, \{d, e\} \}$, which disconnects $G$. Hence $M$ is an edge cutset of $G$.

Edge Connectivity

Similarly to defining vertex connectivity, we will also define edge connectivity.

Definition: For a graph $G = (V(G), E(G))$, if $M$ is an edge cutset, such that $E(G) \backslash M = \{ \{ x, y\} \in E(G) : \{ x, y \} \notin M \}$, and $N$ is an edge cutset such that $E(G) \backslash N = \{ \{ x, y\} \in E(G) : \{ x, y \} \notin N \}$, and $\mid M \mid \leq \mid N \mid$, then the edge connectivity of $G$ denoted $\lambda (G)$ is the least number of edges whose removal disconnects $G$, that is $\lambda (G) = \mid M \mid$.

Once again, in the example from earlier, $M$ was not the smallest edge cutset of $G$. In fact, if $N = \{ a, b\}$, then $E(G) \backslash N$ disconnects $G$, and $| \: N \: | ≤ | \: M \: |$, and in fact, $N$ is the smallest cutset in $G$. Hence $\lambda (G) = | \: N \: | = 1$.

Note that if a graph $G$ has an edge that is a bridge, let's say edge $e = \{ x, y\}$, then the removal of $e$ will result in a disconnected graph by definition. Hence it follows that $\lambda (G) = 1$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License