Graph Connectivity

Connectivity measures how "well-connected" a graph is — how resilient it is to the removal of vertices or edges.

Walks, Paths, Trails, and Cycles

Walk: A sequence of vertices v₀, v₁, ..., vₖ where each consecutive pair (vᵢ, vᵢ₊₁) is an edge. Vertices and edges may repeat.

Trail: A walk with no repeated edges (vertices may repeat).

Path: A walk with no repeated vertices (and therefore no repeated edges).

Closed walk: A walk where v₀ = vₖ (starts and ends at the same vertex).

Circuit: A closed trail (no repeated edges).

Cycle: A closed walk with no repeated vertices except v₀ = vₖ, and length ≥ 3.

Walk:    A → B → C → B → D          (B visited twice)
Trail:   A → B → C → D → B → E      (B visited twice, no edge repeated)
Path:    A → B → C → D → E           (no repetition)
Cycle:   A → B → C → D → A           (closed, no internal repetition)

Lemma: If there is a walk from u to v, there is a path from u to v.

Proof: Take the shortest walk. If a vertex w is repeated, remove the segment between the two occurrences of w. The result is a shorter walk — contradicting minimality. So the shortest walk has no repeated vertices and is a path. ∎

Connected Graphs

Undirected Connectivity

An undirected graph is connected if there is a path between every pair of vertices.

A connected component is a maximal connected subgraph. Every graph is a disjoint union of its connected components.

The number of connected components is denoted c(G) or ω(G).

Properties:

A connected graph with n vertices has at least n - 1 edges.
If a connected graph has exactly n - 1 edges, it is a tree.
Adding an edge can decrease the number of components by at most 1.
Removing an edge can increase the number of components by at most 1.

Directed Connectivity

Strongly connected: For every pair u, v, there is a directed path from u to v and from v to u.

Weakly connected: The underlying undirected graph (ignoring edge directions) is connected.

A strongly connected component (SCC) is a maximal strongly connected subgraph.

The condensation (or DAG of SCCs) is obtained by contracting each SCC to a single vertex. The result is always a DAG.

Algorithms for SCCs

Tarjan's algorithm: Single DFS pass, uses a stack and low-link values. O(V + E).

Kosaraju's algorithm: Two DFS passes — one on G, one on Gᵀ (reversed graph). O(V + E).

Both are covered in detail in the algorithms topic.

Bridges and Articulation Points

Bridge (Cut Edge)

An edge e is a bridge if removing e increases the number of connected components.

Equivalently: e is a bridge iff e is not part of any cycle.

Example: In A—B—C, the edge B—C is a bridge.

Articulation Point (Cut Vertex)

A vertex v is an articulation point if removing v (and its incident edges) increases the number of connected components.

Example: In a star graph, the center is an articulation point.

Finding Bridges and Articulation Points

Using DFS with discovery time and low values:

disc[v]: When v was first discovered.
low[v]: The minimum discovery time reachable from the subtree rooted at v through back edges.

Bridge condition: Edge (u, v) where v is a child of u in the DFS tree is a bridge iff low[v] > disc[u].

Articulation point conditions:

Root of DFS tree: is an articulation point iff it has ≥ 2 children.
Non-root vertex u: is an articulation point iff it has a child v where low[v] ≥ disc[u].

Time: O(V + E).

Biconnected Components

A graph is biconnected (2-connected) if it is connected, has no articulation points, and has ≥ 3 vertices.

Equivalently: For every pair of vertices, there exist at least 2 vertex-disjoint paths between them.

A biconnected component (or block) is a maximal biconnected subgraph, or a bridge (together with its endpoints), or an isolated vertex.

The block-cut tree: Represents the structure of blocks and cut vertices. It is always a tree. Blocks and cut vertices alternate as nodes.

Vertex and Edge Connectivity

Vertex Connectivity κ(G)

The minimum number of vertices whose removal disconnects G (or reduces it to a single vertex).

κ(G) = min |S| such that G - S is disconnected or has ≤ 1 vertex

κ(Kₙ) = n - 1 (must remove all but one vertex)
κ(Cₙ) = 2
κ(tree with ≥ 2 vertices) = 1

k-connected: κ(G) ≥ k. A 2-connected graph has no articulation points.

Edge Connectivity λ(G)

The minimum number of edges whose removal disconnects G.

λ(G) = min |F| such that G - F is disconnected

The minimum edge set that disconnects G is called a minimum edge cut.

λ(Kₙ) = n - 1
λ(Cₙ) = 2
λ(tree) = 1 (any bridge)

Whitney's Inequality

For any graph G:

κ(G) ≤ λ(G) ≤ δ(G)

where δ(G) is the minimum degree.

Intuition: Removing all edges incident to the minimum-degree vertex disconnects it, so λ ≤ δ. Removing end-vertices of a minimum edge cut suffices to disconnect, so κ ≤ λ.

Menger's Theorem

One of the most fundamental results in graph theory, connecting connectivity to disjoint paths.

Vertex Version

The maximum number of vertex-disjoint paths from u to v (for non-adjacent u, v) equals the minimum number of vertices whose removal separates u from v (minimum vertex cut).

Edge Version

The maximum number of edge-disjoint paths from u to v equals the minimum number of edges whose removal separates u from v (minimum edge cut).

Consequence: A graph is k-connected iff every pair of vertices has k vertex-disjoint paths between them.

Menger's theorem is the foundation for network flow algorithms (max-flow min-cut theorem is a weighted generalization).

Euler Paths and Circuits

Euler Trail (Path)

A trail that visits every edge exactly once.

Euler Circuit

A closed trail that visits every edge exactly once.

Euler's Theorem (1736):

A connected graph has an Euler circuit iff every vertex has even degree.
A connected graph has an Euler trail (but not a circuit) iff it has exactly two vertices of odd degree. The trail starts at one odd-degree vertex and ends at the other.

Directed version:

A connected digraph has an Euler circuit iff every vertex has in-degree = out-degree.
An Euler trail exists iff at most one vertex has out-degree - in-degree = 1 (start) and at most one has in-degree - out-degree = 1 (end), and all others are balanced.

Finding an Euler circuit: Hierholzer's algorithm, O(E).

Start at any vertex. Follow edges (removing them) until returning to start.
If unused edges remain at a visited vertex, start a sub-tour there and splice it in.
Repeat until all edges are used.

Hamiltonian Paths and Cycles

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to start.

Unlike Euler paths/circuits, there is no simple characterization of when Hamiltonian paths/cycles exist. Determining existence is NP-complete.

Sufficient conditions (not necessary):

Dirac's Theorem: If n ≥ 3 and every vertex has degree ≥ n/2, then G has a Hamiltonian cycle.

Ore's Theorem: If n ≥ 3 and for every pair of non-adjacent vertices u, v: deg(u) + deg(v) ≥ n, then G has a Hamiltonian cycle.

k-Connectivity in Practice

| k | Meaning | Application | |---|---|---| | 0-connected | Disconnected | Isolated subnetworks | | 1-connected | Connected but has bridges/cut vertices | Single point of failure | | 2-connected | No single point of failure | Redundant paths | | 3-connected | Survives removal of any 2 nodes | Highly reliable networks | | k-connected | Survives removal of any k-1 nodes | Fault tolerance |

Real-World Applications

Network reliability: Vertex/edge connectivity measures resilience. Internet backbone design targets high connectivity.
Routing: Multiple vertex-disjoint paths enable fault-tolerant routing and load balancing.
Social network analysis: Articulation points identify influential connectors. Biconnected components find tightly-knit groups.
Circuit design: Bridges represent critical connections. Redundancy requires higher connectivity.
Transportation: Euler circuits solve the Chinese postman problem (mail delivery visiting every street). Hamiltonian circuits model TSP.
Bioinformatics: De Bruijn graphs (for genome assembly) use Euler paths through the graph of k-mers.
Compiler analysis: Dominators in control flow graphs use connectivity concepts. Loop detection uses back edges and SCCs.