[null, {"document_url": "http://mathonline.wikidot.com/vertex-and-edge-cutsets", "unformatted_src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-29%20at%2011.47.17%20PM.png", "src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-29%20at%2011.47.17%20PM.png", "formatted_filename": "Screen Shot at", "alt_text": "Screen%20Shot%202014-03-29%20at%2011.47.17%20PM.png"}, null, {"document_url": "http://mathonline.wikidot.com/vertex-and-edge-cutsets", "unformatted_src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-29%20at%2011.47.40%20PM.png", "src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-29%20at%2011.47.40%20PM.png", "formatted_filename": "Screen Shot at", "alt_text": "Screen%20Shot%202014-03-29%20at%2011.47.40%20PM.png"}, null, {"document_url": "http://mathonline.wikidot.com/vertex-and-edge-cutsets", "unformatted_src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-30%20at%2012.29.52%20AM.png", "src": "http://mathonline.wdfiles.com/local--files/vertex-and-edge-cutsets/Screen%20Shot%202014-03-30%20at%2012.29.52%20AM.png", "formatted_filename": "Screen Shot at", "alt_text": "Screen%20Shot%202014-03-30%20at%2012.29.52%20AM.png"}, null]
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

For example, let's look at the following graph: 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: Hence, $W$ is indeed a vertex cutset of $G$ since the resulting graph is disconnected.

Vertex Connectivity

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

Essentially, edge cutsets are the same thing as vertex cutsets with relevance only to edges. For example, in the following graph: 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.

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$.