Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 15.4 Articulation 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
🔗

Example 15.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.
A graph featuring a single, central articulation vertex.
Figure 15.4.2. A graph featuring a single, central articulation vertex.
🔗

Example 15.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.
A graph featuring a bridge between two articulation vertices.
Figure 15.4.4. A graph featuring a bridge between two articulation vertices.
🔗

Remark 15.4.5.

🔗
In the proof of Theorem 15.3.11, our conception was that “extra” vertex v0 was an articulation vertex, where removing it would create a subgraph G′ that would be split into connected components G1′,…,Gℓ′. (Though it is possible v0 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
🔗

Remark 15.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.
🔗

Example 15.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. For example, removing the single edge e in the graph of Figure 15.4.4 breaks the graph into two nonconnected subgraphs.
First, if v is a vertex of G with deg⁡v=d, 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.
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
2e=deg⁡v1+deg⁡v2+⋯+deg⁡vn≥d+d+⋯+d=nd.
So d≤2e/n. The number 2e/n is rational, but may not be an integer. However, d is definitely an integer, so we must have d≤⌊2e/n⌋. Since we have already concluded that the edge connectivity of G is no greater than d, it also can be no greater than ⌊2e/n⌋.
🔗

Remark 15.4.10.

🔗
With n and e as in the statement of the theorem, 2e is equal to the sum of the degrees of the vertices (Theorem 14.2.4), so 2e/n is equal to the average degree of vertices in the graph.
🔗

Worked Example 15.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?
A communication network.
Figure 15.4.12. TreeFort CommNet.
Solution.
There are 6 nodes and 10 edges, so Proposition 15.4.9 tells that the edge connectivity must be no greater than ⌊20/6⌋=3. 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.
<Prev^TopNext>