Connectivity

Introduction

Connectivity measures how well a graph is connected. It’s crucial for understanding network reliability, communication paths, and graph structure.

Connected Graphs

Definition

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

Example - Connected:

1 --- 2
|     |
3 --- 4

Every vertex can reach every other vertex.

Example - Disconnected:

1 --- 2     5 --- 6

No path between {1,2} and {5,6}.

Connected Components

Definition

A connected component is a maximal connected subgraph.

Example:

1 --- 2     5 --- 6
|           |
3           7

Component 1: {1, 2, 3}
Component 2: {5, 6, 7}

Finding Connected Components

Algorithm (using DFS):

1. Start with any unvisited vertex
2. Do DFS to mark all reachable vertices
3. All marked vertices form one component
4. Repeat for unvisited vertices

Time Complexity: O(V + E)

Connectivity in Directed Graphs

Strongly Connected

A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.

Example - Strongly Connected:

1 → 2
↑   ↓
← 3

Can reach any vertex from any other following arrows.

Example - NOT Strongly Connected:

1 → 2 → 3

Cannot reach 1 from 3.

Weakly Connected

A directed graph is weakly connected if the underlying undirected graph is connected (ignore edge directions).

Example:

1 → 2 → 3

• Weakly connected (ignoring directions)
• NOT strongly connected

Strongly Connected Components (SCCs)

Definition: Maximal strongly connected subgraphs.

Example:

1 → 2 → 3
↑   ↓   ↓
← 4     5

SCCs: {1, 2, 4}, {3}, {5}

Kosaraju’s Algorithm:

1. Do DFS on graph, note finish times
2. Transpose graph (reverse all edges)
3. Do DFS on transposed graph in decreasing finish time order
4. Each DFS tree in step 3 is an SCC

Time Complexity: O(V + E)

Cut Vertices (Articulation Points)

Definition

A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components.

Example:

1 --- 2 --- 3
      |
      4

Vertex 2 is a cut vertex. Removing it disconnects the graph into {1} and {3, 4}.

Why Important?

Cut vertices are critical points in networks:

• Removing them breaks connectivity
• Single points of failure
• Important for network reliability

Finding Cut Vertices

Properties:

• Root of DFS tree is cut vertex if it has > 1 child
• Non-root vertex v is cut vertex if it has a child subtree with no back edge to an ancestor of v

Algorithm (using DFS):

• Track discovery time and lowest reachable ancestor
• Check for back edges

Time Complexity: O(V + E)

Example: Finding Cut Vertices

Graph:
    1
   / \
  2   3
 / \
4   5

DFS from 1:

• 1 is root with 2 children → cut vertex
• 2 has children but all have back edges → not cut vertex

Result: Only 1 is a cut vertex

Cut Edges (Bridges)

Definition

A cut edge (or bridge) is an edge whose removal increases the number of connected components.

Example:

1 --- 2 --- 3 --- 4
      |
      5

Edge {2, 3} is a bridge. Removing it disconnects the graph.

Properties

• Every bridge is a single-edge cut
• Graph with no bridges is called bridge-connected
• Tree edges are bridges if removing them disconnects the tree

Finding Bridges

Algorithm (using DFS):

• An edge (u, v) is a bridge if there’s no back edge from v’s subtree that goes to an ancestor of u
• Track discovery time and lowest reachable vertex

Time Complexity: O(V + E)

Vertex Connectivity

Definition

The vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects the graph.

Examples:

Path graph (1---2---3):

• κ = 1 (remove middle vertex)

Cycle C₄:

• κ = 2 (need to remove 2 vertices)

Complete graph Kₙ:

• κ = n-1 (need to remove all but one)

k-Connected Graphs

A graph is k-connected if κ(G) ≥ k.

Properties:

• 1-connected = connected
• 2-connected = no cut vertices
• 3-connected = removing any 2 vertices keeps it connected

Menger’s Theorem

Theorem: A graph is k-connected if and only if every pair of vertices has at least k vertex-disjoint paths between them.

Vertex-disjoint paths: Paths that don’t share any internal vertices.

Edge Connectivity

Definition

The edge connectivity λ(G) is the minimum number of edges whose removal disconnects the graph.

Examples:

Tree: λ = 1 (any edge removal disconnects it)

Cycle: λ = 2 (need to cut 2 edges)

Complete graph Kₙ: λ = n-1

k-Edge-Connected Graphs

A graph is k-edge-connected if λ(G) ≥ k.

Relationship

Always true: κ(G) ≤ λ(G) ≤ δ(G)

Where δ(G) = minimum vertex degree

Why?

• Removing all edges at min-degree vertex disconnects it
• Can always remove adjacent vertices instead of edges

2-Connected Graphs

Definition

A graph is 2-connected (biconnected) if:

• It has no cut vertices
• Removing any single vertex keeps it connected

Properties

• Every pair of vertices lies on a common cycle
• Minimum vertex connectivity is 2
• Important for reliable networks

Block

A block is a maximal 2-connected subgraph.

Example:

1 --- 2 --- 3 --- 4
      |     |
      5 --- 6

Blocks: {1,2,5}, {2,3,5,6}, {3,4,6}

Practical Applications

Network Reliability

Cut vertices/edges identify weak points:

• Internet routing (routers that are single points of failure)
• Power grids (stations whose failure causes blackouts)
• Transportation networks (critical bridges)

Social Networks

Connectivity measures:

• Community structure
• Information flow
• Influence propagation

Communication Networks

k-connectivity ensures:

• Fault tolerance (can lose k-1 nodes/edges)
• Alternative paths
• Robustness

Algorithms Summary

Example Problems

Problem 1: Count Components

Graph:

1 --- 2     4 --- 5     7
|           |
3           6

Solution:

• Component 1: {1, 2, 3}
• Component 2: {4, 5, 6}
• Component 3: {7}
• Answer: 3 components

Problem 2: Find Cut Vertices

Graph:

    1
   /|\
  2 3 4

Solution:

• Remove 1: Graph becomes {2}, {3}, {4} (disconnected)
• Remove 2, 3, or 4: Still connected
• Answer: Vertex 1 is the only cut vertex

Problem 3: Edge Connectivity

Graph: Cycle C₅

Solution:

• Need to remove at least 2 edges to disconnect
• Answer: λ(C₅) = 2

Key Points for Exams

1. Connected: path exists between all vertex pairs
2. Component: maximal connected subgraph
3. Strongly connected (directed): directed path between all pairs
4. Weakly connected: underlying undirected is connected
5. Cut vertex: removal increases components
6. Bridge: edge whose removal increases components
7. Vertex connectivity κ(G): min vertices to remove
8. Edge connectivity λ(G): min edges to remove
9. Inequality: κ(G) ≤ λ(G) ≤ δ(G)
10. 2-connected: no cut vertices

Practice Problems

1. How many connected components in a graph with edges: {1,2}, {3,4}, {5,6}?

2. Is a tree 2-connected? Why or why not?

3. Find all cut vertices in: 1---2---3---4

4. What is the edge connectivity of K₅?

5. Prove that every bridge is a cut edge but not every cut edge is a bridge.

6. In a cycle Cₙ, how many vertices must be removed to disconnect it?

7. Is strongly connected → weakly connected? Is the converse true?

8. Draw a 3-connected graph with 6 vertices.

9. Can a graph be 3-edge-connected but only 2-vertex-connected? Give example.

10. Use DFS to find connected components in graph with edges: {1,2}, {2,3}, {4,5}