Mathematics.

graph structures

Graph Connectivity

Graph Theory25 minDifficulty3 out of 10

You should know: graph basics, graph traversal

Overview

A graph is connected if there is a path between every pair of vertices; otherwise it splits into two or more connected components, each a maximal set of mutually reachable vertices. Connectivity can be measured more finely: vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects the graph (or reduces it to a single vertex), and edge connectivity λ(G) is the analogous minimum number of edges. A single vertex whose removal disconnects the graph is called a cut vertex (or articulation point), and a single edge with the same effect is a bridge. These measures quantify network robustness — how many failures a network can tolerate before it fragments.

Intuition

Think of a connectivity as measuring how many single points of failure a network has. A power grid where removing one substation splits the network into two dark regions has a cut vertex — a weak point. Airline route maps, the internet backbone, and road networks are all engineered to keep vertex and edge connectivity high, precisely so that no single failure (or small set of failures) can cut the network in two.

Formal Definition

Definition

For an undirected graph G = (V, E):

G is connected  ⟺  ∀u,v∈V, ∃ a path from u to vG \text{ is connected} \iff \forall u,v \in V,\ \exists \text{ a path from } u \text{ to } v
Connectivity definition
κ(G)=min⁡{∣S∣:S⊆V, G−S is disconnected or trivial}\kappa(G) = \min\{|S| : S \subseteq V,\ G - S \text{ is disconnected or trivial}\}
Vertex connectivity
λ(G)=min⁡{∣F∣:F⊆E, G−F is disconnected}\lambda(G) = \min\{|F| : F \subseteq E,\ G - F \text{ is disconnected}\}
Edge connectivity
κ(G)≤λ(G)≤δ(G)\kappa(G) \le \lambda(G) \le \delta(G)
Whitney's inequality (δ = minimum degree)

Worked Examples

  1. Starting from A, traversal reaches B (via A-B) then C (via B-C); no edge connects this group to D or E.

    {A,B,C}\{A, B, C\}

  2. D and E are connected to each other via D-E, but to nothing else.

    {D,E}\{D, E\}

Answer: 2 connected components: {A,B,C} and {D,E}.

Practice Problems

Difficulty 3/10

A graph has vertices {1,2,3,4} and edges 1-2, 3-4. How many connected components does it have?

Difficulty 4/10

A company's office network has two buildings connected by exactly one network cable running through a single router. If that router fails, the two buildings can no longer communicate. What graph-theoretic concept describes this router?

Difficulty 5/10

A graph has minimum degree δ(G) = 3. What is the maximum possible value of its vertex connectivity κ(G)?

Quiz

A cut vertex (articulation point) is a vertex whose removal:
Whitney's inequality relates vertex connectivity κ, edge connectivity λ, and minimum degree δ as:
A network engineer wants no single cable failure to split the network. This requires:

Summary

  • A graph is connected if every pair of vertices has a path between them; otherwise it splits into connected components.
  • Cut vertices and bridges are single points of failure — removing them disconnects the graph.
  • Vertex connectivity κ(G) and edge connectivity λ(G) quantify robustness, satisfying κ(G) ≤ λ(G) ≤ δ(G).

References

  1. WebsiteWikipedia — Connectivity (graph theory)