Graph Connectivity: short notes (Engineering Mathematics)

Introduction

A network is useful only if its parts can reach each other, and it is robust only if it stays connected when something fails. Connectivity makes both ideas precise: whether paths exist between vertices, how a graph splits into connected pieces, and how many vertices or edges must be removed to disconnect it. These questions arise in network design (single points of failure), in algorithms (breadth-first and depth-first search find components, cut vertices and bridges in linear time) and in minimum spanning trees.

Prerequisites

Graph Theory Fundamentals: degree, paths, cycles, trees, complements. Graphs are simple and undirected unless stated.

Core concepts

Connected graphs and components

Vertices $u$ and $v$ are connected if there is a path between them. This is an equivalence relation on $V$ ; its classes are the connected components.
$G$ is connected if it has exactly one component. The number of components is written $c(G)$ or $\omega(G)$ .
The distance $d(u, v)$ is the length of a shortest path. The eccentricity of $v$ is $\max_u d(u, v)$ ; the diameter is the largest eccentricity and the radius the smallest. $\text{rad}(G) \le \text{diam}(G) \le 2\,\text{rad}(G)$ .

Edge counts and connectivity

For a simple graph with $n$ vertices:

Statement	Bound
Connected needs at least	$n - 1$ edges (a tree attains it)
With $k$ components, at least	$n - k$ edges
With $k$ components, at most	$\binom{n - k + 1}{2}$ edges
A disconnected graph has at most	$\binom{n-1}{2}$ edges
So any graph with more than $\binom{n-1}{2}$ edges is	connected

The maximum for $k$ components is attained by $K_{n-k+1}$ plus $k - 1$ isolated vertices: concentrating vertices in one clique maximises edges, since $\binom{a}{2} + \binom{b}{2} \le \binom{a+b-1}{2}$ for $a, b \ge 1$ .

Degree condition. If $\delta(G) \ge (n-1)/2$ , then $G$ is connected (two non-adjacent vertices have more than $n - 2$ neighbours between them among the other $n - 2$ vertices, so they share a neighbour). The bound is tight: two disjoint copies of $K_{n/2}$ have $\delta = n/2 - 1$ .

Cut vertices and bridges

A cut vertex (articulation point) is a vertex whose removal (with its incident edges) increases the number of components.
A bridge (cut edge) is an edge whose removal increases the number of components.
An edge is a bridge if and only if it lies on no cycle. Every edge of a tree is a bridge.
A vertex $v$ is a cut vertex exactly when some distinct $u,w\ne v$ lie in the same component of $G$ , but are disconnected in $G-v$ ; equivalently a $u$ - $w$ path exists and every such path passes through $v$ .
If $\{u, v\}$ is a bridge and $\deg(u) \ge 2$ , then $u$ is a cut vertex. The converse fails: a cut vertex need not be incident to any bridge (the shared vertex of two triangles joined at one vertex, the "bowtie").
Every non-trivial connected graph has at least two vertices that are not cut vertices (the ends of a longest path).

A connected graph with no cut vertex (and at least 3 vertices) is 2-connected (biconnected). The maximal 2-connected pieces and bridges are its blocks. A graph with $n \ge 3$ is 2-connected if and only if every two vertices lie on a common cycle (Whitney).

Cut vertices, bridges, and connectivity numbers — Figure 1. A graph with its cut vertices and bridge highlighted, and a second graph showing $\kappa = 1$ , $\lambda = 2$ , $\delta = 3$ , so that the inequality $\kappa \le \lambda \le \delta$ is strict.

Vertex and edge connectivity

The vertex connectivity $\kappa(G)$ is the minimum number of vertices whose removal disconnects $G$ or leaves a single vertex. $\kappa(K_n) = n - 1$ by convention, since no set of vertices disconnects a complete graph.
The edge connectivity $\lambda(G)$ of a graph with $n \ge 2$ vertices is the minimum number of edges whose removal disconnects $G$ .
$G$ is $k$ -connected if $\kappa(G) \ge k$ , and $k$ -edge-connected if $\lambda(G) \ge k$ .
$\kappa(G) = 0$ if and only if $G$ is disconnected (or trivial); $\kappa(G) = 1$ if and only if $G$ is connected with a cut vertex (or $G = K_2$ ); $\lambda(G) = 1$ if and only if $G$ is connected with a bridge.

Whitney's inequality:

\kappa(G) \le \lambda(G) \le \delta(G).

The right inequality holds because removing all edges at a minimum-degree vertex isolates it. Both inequalities can be strict.

Graph	$\kappa$	$\lambda$	$\delta$
$K_n$	$n - 1$	$n - 1$	$n - 1$
$C_n$	2	2	2
Tree with $n \ge 3$	1	1	1
$K_{r,s}$ , $r \le s$	$r$	$r$	$r$
$Q_k$	$k$	$k$	$k$
Two $K_4$ sharing one vertex	1	3	3

Menger's theorem (stated for reference): for non-adjacent $u, v$ , the minimum number of vertices separating them equals the maximum number of internally vertex-disjoint $u$ - $v$ paths; the edge version is the same with edges. This links connectivity to network flows.

Directed graphs

A digraph is strongly connected if every vertex can reach every other along directed paths, and weakly connected if its underlying undirected graph is connected.
The strongly connected components (SCCs) partition the vertices; contracting each SCC to one vertex gives a directed acyclic graph (the condensation). SCCs are found in $O(n + m)$ time (Kosaraju's or Tarjan's algorithm).
A strongly connected digraph on $n \ge 2$ vertices has at least $n$ arcs (a directed cycle attains it).

Counting spanning trees

A spanning tree of a connected graph is a spanning subgraph that is a tree; it has $n - 1$ edges. Every connected graph has one.

Cayley's formula: $K_n$ has $n^{n-2}$ spanning trees (equivalently, there are $n^{n-2}$ labelled trees on $n$ vertices).
$K_{r,s}$ has $r^{s-1} s^{r-1}$ spanning trees. $C_n$ has $n$ .
Kirchhoff's matrix-tree theorem: the number of spanning trees equals any cofactor of the Laplacian $L = D - A$ , where $D$ is the diagonal degree matrix and $A$ the adjacency matrix (delete row $i$ and column $i$ , take the determinant).

Worked examples

Example 1: forced connectivity

What is the minimum number of edges that guarantees a simple graph on 10 vertices is connected? A disconnected graph has at most $\binom{9}{2} = 36$ edges, so 37 edges guarantee connectivity.

Example 2: components and edges

A simple graph with 12 vertices has 3 components. Minimum edges: $12 - 3 = 9$ . Maximum: $\binom{12 - 3 + 1}{2} = \binom{10}{2} = 45$ .

Example 3: forests

A forest with 20 vertices and 14 edges has $20 - 14 = 6$ components (each tree component has one fewer edge than vertices).

Example 4: matrix-tree theorem

For $K_4$ minus one edge (vertices 1, 2, 3, 4; edge $\{3, 4\}$ missing), the Laplacian is

L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \end{pmatrix}.

Deleting row 1 and column 1: $\det \begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & 0 \\ -1 & 0 & 2 \end{pmatrix} = 3 \cdot 4 - (-1)(-2) + (-1)(2) = 12 - 2 - 2 = 8$ . So it has 8 spanning trees, compared with $4^2 = 16$ for $K_4$ . (Check: the 16 trees of $K_4$ split evenly over its 6 edges with $3 \cdot 16 / 6 = 8$ containing any given edge, leaving $16 - 8 = 8$ that avoid it.)

Important properties and observations

Removing a cut vertex can create many components (the centre of a star $K_{1,s}$ creates $s$ ); removing a bridge creates exactly one more.
A connected graph with $n$ vertices and $n - 1$ edges is a tree; with $n$ edges it has exactly one cycle.
$G$ or $\overline{G}$ is connected; if $G$ is disconnected, $\overline{G}$ has diameter at most 2.
A 3-regular graph has $\kappa = \lambda$ .
An Euler graph (all degrees even) has no bridges.

GATE examination perspective

Edge-bound questions. Maximum edges with $k$ components, minimum edges to force connectivity: $\binom{n-1}{2} + 1$ .
Forest component counts. Components $= n - m$ .
Cut vertex and bridge identification. A bridge lies on no cycle; check whether removing a vertex separates two others.
$\kappa \le \lambda \le \delta$ . Expect true or false statements; know a strict example.
Spanning-tree counts. Cayley $n^{n-2}$ , $K_{r,s}$ , matrix-tree theorem for small graphs.
Trap: a graph with $n - 1$ edges need not be connected; it is a tree only if it is also connected (or acyclic).

Summary

Graph Theory Fundamentals: prerequisite.
Breadth-First Search: related. Components and distances in unweighted graphs.
Depth-First Search: related. Cut vertices, bridges and SCCs in linear time.
Minimum Spanning Trees: related. Spanning trees of minimum weight.
Determinants: related. The matrix-tree theorem uses a determinant.

Graph Connectivity

Introduction

Prerequisites

Core concepts

Connected graphs and components

Edge counts and connectivity

Cut vertices and bridges

Vertex and edge connectivity

Directed graphs

Counting spanning trees

Worked examples

Example 1: forced connectivity

Example 2: components and edges

Example 3: forests

Example 4: matrix-tree theorem

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Connected graphs and components

Edge counts and connectivity

Cut vertices and bridges

Vertex and edge connectivity

Directed graphs

Counting spanning trees

Worked examples

Example 1: forced connectivity

Example 2: components and edges

Example 3: forests

Example 4: matrix-tree theorem

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps