Section15.4Articulation vertices, bridges, and edge connectivity
articulation vertex
a vertex of a graph such that, if it were to be removed (along with any edges incident to it), the resulting subgraph would have more connected components than the original
bridge
an edge of a graph such that, if it were to be removed, the resulting subgraph would have more connected components than the original
Example15.4.1.An articulation vertex.
In the graph of Figure 15.4.2, the central vertex that is common to both diamond-shaped subgraphs is an articulation vertex, as removing it and all edges incident to it would leave two unconnected “ears” on the outside of the two diamond shapes.
Figure15.4.2.A graph featuring a single, central articulation vertex.
Example15.4.3.A bridge between two articulation vertices.
In the graph of Figure 15.4.4, edge \(e\) is a bridge, and each of \(v\) and \(v'\) are articulation vertices.
Figure15.4.4.A graph featuring a bridge between two articulation vertices.
Remark15.4.5.
In the proof of Theorem 15.3.11, our conception was that “extra” vertex \(v_0\) was an articulation vertex, where removing it would create a subgraph \(G'\) that would be split into connected components \(G_1', \dotsc, G_\ell'\text{.}\) (Though it is possible \(v_0\) is not an articulation vertex, if subgraph \(G'\) is connected.)
edge connectivity
the minimum number of edges that must be removed from a connected graph to obtain a nonconnected subgraph
Remark15.4.6.
Edge connectivity measures redundancy in the graph, as each edge that can be removed without breaking the graph into nonconnected subgraphs must be incident to a pair of vertices that remain connected via some other walk through the graph.
Example15.4.7.
The edge connectivity of the graph in Figure 15.4.2 is \(2\text{.}\)
Example15.4.8.Edge connectivity in a graph with a bridge.
A bridge represents a “single point of failure,” and every graph that contains a bridge has edge connectivity \(1\text{.}\) For example, removing the single edge \(e\) in the graph of Figure 15.4.4 breaks the graph into two nonconnected subgraphs.
Proposition15.4.9.Two upper bounds for edge connectivity.
Suppose \(G = (V,E)\) is a connected graph. Let \(n = \abs{V}\text{,}\)\(e = \abs{E}\text{,}\) and let \(d\) be the smallest degree of any of the vertices of \(G\text{.}\) Then the edge connectivity of \(G\) cannot be greater than either of the integers \(d\) or \(\floor{2 e / n}\text{.}\)
First, if \(v\) is a vertex of \(G\) with \(\deg v = d\text{,}\) then removing all of the edges incident to \(v\) will cause \(v\) to become isolated and \(G\) to become nonconnected. So the edge connectivity of \(G\) cannot be greater than \(d\text{.}\)
Next, recall that the sum of the degrees of the vertices of \(G\) is equal to \(2e\) (Theorem 14.2.4). Using this, we have
\begin{equation*}
2e = \deg v_1 + \deg v_2 + \dotsb + \deg v_n \ge d + d + \dotsb + d = nd \text{.}
\end{equation*}
So \(d \le 2 e / n\text{.}\) The number \(2e/n\) is rational, but may not be an integer. However, \(d\) is definitely an integer, so we must have \(d \le \floor{2e/n}\text{.}\) Since we have already concluded that the edge connectivity of \(G\) is no greater than \(d\text{,}\) it also can be no greater than \(\floor{2 e / n}\text{.}\)
Remark15.4.10.
With \(n\) and \(e\) as in the statement of the theorem, \(2 e\) is equal to the sum of the degrees of the vertices (Theorem 14.2.4), so \(2 e / n\) is equal to the average degree of vertices in the graph.
Worked Example15.4.11.
Your tree fort rivals have set up a communication system of tin cans and strings. You have mapped out their network as in Figure 15.4.12. To minimize the risk of crab apple welts, what is the minimum number of strings you must cut to disrupt their communications?
There are \(6\) nodes and \(10\) edges, so Proposition 15.4.9 tells that the edge connectivity must be no greater than \(\floor{20/6} = 3\text{.}\) By inspection, the edge connectivity is not \(1\) as there are no bridges. However, we may isolate either fort ALPHA or ECHO with two snips.
