Chapter 8. Connected Graphs

A graph is connected when its vertices belong to one piece. More precisely, an undirected graph is connected if every pair of vertices can be joined by a path. If this condition fails, the graph is disconnected and separates into connected components. Standard texts define connectedness through paths and treat connected components as maximal connected subgraphs.

Connectedness is a global property. Degree describes the immediate neighborhood of one vertex. Connectedness describes whether the whole graph can be traversed from any starting vertex.

8.1 Connected Vertices

Let

G = (V,E)

be an undirected graph. Two vertices $u,v \in V$ are connected if there exists a path from $u$ to $v$ .

This means that there is a sequence

u = v_0, v_1, \ldots, v_k = v

such that

\{v_{i-1},v_i\} \in E

for every

1 \leq i \leq k.

The path may have length $0$ . Thus every vertex is connected to itself.

8.2 Connected Graphs

A graph $G$ is connected if every pair of vertices in $G$ is connected.

Equivalently, $G$ is connected if for all $u,v \in V(G)$ , there exists a path from $u$ to $v$ .

For example, the path graph

P_5

is connected. Its vertices can be arranged as

v_1,v_2,v_3,v_4,v_5,

with edges

\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}, \{v_4,v_5\}.

Any vertex can reach any other vertex by moving along the path.

The complete graph

K_n

is connected for every

n \geq 1.

Every pair of distinct vertices is joined by an edge, so every pair is joined by a path of length $1$ .

8.3 Disconnected Graphs

A graph is disconnected if it is not connected.

Thus a graph is disconnected if there exist vertices $u$ and $v$ such that no path joins $u$ to $v$ .

For example, let

V=\{a,b,c,d,e\}

and

E=\{\{a,b\}, \{b,c\}, \{d,e\}\}.

There is a path from $a$ to $c$ , and there is a path from $d$ to $e$ . But there is no path from $a$ to $d$ . Therefore the graph is disconnected.

Disconnected graphs consist of separate connected pieces.

8.4 Connected Components

A connected component of a graph is a maximal connected subgraph.

Maximal means that no more vertices or edges from the original graph can be added while preserving connectedness.

In the graph

V=\{a,b,c,d,e\}

and

E=\{\{a,b\}, \{b,c\}, \{d,e\}\},

the connected components have vertex sets

\{a,b,c\}

and

\{d,e\}.

The first component contains the path

a,b,c.

The second component contains the edge

\{d,e\}.

There is no edge or path connecting the two components.

8.5 Components as Equivalence Classes

Connectedness among vertices is an equivalence relation.

It is reflexive because every vertex is connected to itself by a path of length $0$ .

It is symmetric because in an undirected graph, any path from $u$ to $v$ can be read backward as a path from $v$ to $u$ .

It is transitive because if there is a path from $u$ to $v$ , and a path from $v$ to $w$ , then joining the two paths gives a walk from $u$ to $w$ . Removing repeated vertices gives a path from $u$ to $w$ .

Therefore connectedness partitions the vertex set into equivalence classes. These equivalence classes are exactly the connected components. Each vertex belongs to exactly one connected component.

8.6 Number of Components

The number of connected components of $G$ is often written as

c(G).

A graph is connected exactly when

c(G)=1.

A graph with no edges and $n$ vertices has

c(G)=n,

because every vertex forms its own component.

A null graph, if allowed, has no vertices. Depending on convention, its number of components may be taken as $0$ .

8.7 Isolated Vertices

An isolated vertex is a vertex of degree $0$ .

Every isolated vertex forms a connected component by itself. If

\deg(v)=0,

then no edge is incident with $v$ , so no path of positive length can begin at $v$ . The only vertex reachable from $v$ is $v$ itself.

Thus an isolated vertex prevents a graph with more than one vertex from being connected.

For example, if

V=\{a,b,c\}

and

E=\{\{a,b\}\},

then $c$ is isolated. The graph has two components:

\{a,b\}

and

\{c\}.

8.8 Connected Subgraphs

A subgraph $H$ of $G$ is connected if every pair of vertices in $H$ can be joined by a path using only vertices and edges of $H$ .

A connected component is a connected subgraph that is maximal with respect to inclusion.

The word maximal is important. A connected subgraph may be contained in a larger connected subgraph.

For example, in the path

a,b,c,d,

the subgraph on vertices

\{a,b,c\}

is connected. But it is not a connected component of the whole graph, because it can be enlarged by adding $d$ and the edge $\{c,d\}$ .

8.9 Spanning Connected Subgraphs

A subgraph is spanning if it contains every vertex of the original graph.

A graph $G$ is connected exactly when it has a connected spanning subgraph.

For example, every connected graph has a spanning tree. A spanning tree contains all vertices and enough edges to connect them without forming cycles.

This fact links connectedness with trees. Later chapters will show that a graph is connected if and only if it has a spanning tree.

8.10 Paths and Connectedness

Connectedness is defined by paths, but walks give an equivalent condition.

If there is a walk from $u$ to $v$ , then there is a path from $u$ to $v$ . Repeated vertices can be removed from the walk until no vertex repeats.

Therefore a graph is connected if every pair of vertices is joined by a walk.

This version is often useful in proofs. One may naturally construct a walk first, then reduce it to a path.

8.11 Distance in Connected Graphs

In a connected graph, the distance between any two vertices is finite.

The distance from $u$ to $v$ is

d(u,v),

the length of a shortest path from $u$ to $v$ .

Since the graph is connected, such a path always exists.

Distances in a connected graph satisfy the usual metric properties:

d(u,v) \geq 0,

d(u,v)=0 \iff u=v,

d(u,v)=d(v,u),

and

d(u,w) \leq d(u,v)+d(v,w).

The last inequality is the triangle inequality. It follows by joining a shortest path from $u$ to $v$ with a shortest path from $v$ to $w$ , then observing that the shortest path from $u$ to $w$ cannot be longer than that walk.

8.12 Diameter

The diameter of a connected graph is the largest distance between any two vertices:

\operatorname{diam}(G) = \max_{u,v \in V(G)} d(u,v).

The diameter measures how far apart the most distant vertices are.

For the path graph $P_n$ ,

\operatorname{diam}(P_n)=n-1.

For the complete graph $K_n$ , with $n \geq 2$ ,

\operatorname{diam}(K_n)=1.

A small diameter means that every vertex is close to every other vertex. This is common in many communication and social network models.

8.13 Radius and Center

The eccentricity of a vertex $v$ in a connected graph is

\operatorname{ecc}(v) = \max_{u \in V(G)} d(v,u).

It is the greatest distance from $v$ to any other vertex.

The radius of $G$ is

\operatorname{rad}(G) = \min_{v \in V(G)} \operatorname{ecc}(v).

A center of $G$ is a vertex whose eccentricity equals the radius.

The center consists of vertices that are as close as possible to the whole graph.

In a path graph, the center is the middle vertex if the path has odd order, and the two middle vertices if the path has even order.

8.14 Bridges and Connectedness

An edge whose removal increases the number of connected components is called a bridge or cut edge.

If $e$ is a bridge, then

c(G-e) > c(G).

In a connected graph, this means that $G-e$ is disconnected.

Bridges are edges that carry essential connectivity. They do not lie on cycles. If an edge lies on a cycle, then removing it still leaves an alternate route around the rest of the cycle.

For example, in a tree, every edge is a bridge. In a cycle graph $C_n$ , no edge is a bridge.

8.15 Cut Vertices

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

If $v$ is a cut vertex, then removing $v$ and all edges incident with it separates the graph into more pieces.

Cut vertices are important in network reliability. They identify single points whose failure can disconnect a system.

In the path graph

v_1,v_2,v_3,v_4,

the vertices $v_2$ and $v_3$ are cut vertices. Removing either one disconnects the graph.

The endpoints $v_1$ and $v_4$ are not cut vertices.

8.16 Connectedness and Minimum Edges

A connected graph with $n$ vertices must have at least

n-1

edges.

This lower bound is attained by trees.

Proof

Start with one vertex. Each time an edge is used to bring in a new vertex, at most one new vertex can be added to the connected part. To connect all $n$ vertices, at least $n-1$ such additions are required.

Equivalently, every connected graph contains a spanning tree, and every tree on $n$ vertices has $n-1$ edges.

Thus no graph with fewer than $n-1$ edges can be connected.

8.17 Connectedness and Maximum Components

If a graph has $n$ vertices and $m$ edges, then each edge can reduce the number of components by at most $1$ .

Starting from the empty graph on $n$ vertices, there are $n$ components. Adding one edge can join two components, reducing the count by $1$ , or it can lie inside an existing component, leaving the count unchanged.

Therefore

c(G) \geq n-m.

This bound is useful for quick impossibility arguments. If

m < n-1,

then

c(G) \geq n-m > 1,

so $G$ is disconnected.

8.18 Connectedness in Directed Graphs

Directed graphs require more than one notion of connectedness.

A directed graph is strongly connected if for every ordered pair of vertices $u,v$ , there is a directed path from $u$ to $v$ .

It is weakly connected if the underlying undirected graph is connected after ignoring edge directions.

Strong connectedness requires two-way reachability. Weak connectedness only requires connection after directions are forgotten. These two notions are standard for directed graphs.

For example, the directed path

a \to b \to c

is weakly connected but not strongly connected. There is a directed path from $a$ to $c$ , but no directed path from $c$ to $a$ .

8.19 Testing Connectedness

In a finite graph, connectedness can be tested by graph traversal.

Choose a starting vertex $s$ . Run breadth-first search or depth-first search from $s$ . If every vertex is reached, the graph is connected. If some vertex is not reached, the graph is disconnected.

For a graph stored by adjacency lists, this takes time

O(|V|+|E|).

The traversal visits each vertex at most once and examines each edge a bounded number of times.

The same traversal also finds the connected component containing $s$ . Repeating the process from unvisited vertices finds all connected components.

8.20 Example

Let

V=\{a,b,c,d,e,f,g\}

and

E= \{\{a,b\},\{b,c\},\{c,a\},\{d,e\},\{e,f\}\}.

The vertices $a,b,c$ form one component. They are mutually connected, and they form a triangle.

The vertices $d,e,f$ form a second component. They form a path.

The vertex $g$ is isolated and forms a third component.

Thus

c(G)=3.

The graph is disconnected because more than one component exists.

8.21 Summary

A graph is connected if every pair of vertices is joined by a path. Connectedness is an equivalence relation on vertices, and its equivalence classes are the connected components. A graph is connected exactly when it has one component.

Connected graphs have finite distances between all vertex pairs. This leads to diameter, radius, eccentricity, and center. Edges or vertices whose removal destroys connectedness are bridges and cut vertices.

Connectedness is one of the basic global properties of a graph. It separates graphs that form one coherent structure from graphs that split into independent pieces.