Connected Graph — Definition, Formula & Examples

A connected graph is a graph in which there exists at least one path between every pair of vertices. If any vertex is unreachable from another, the graph is disconnected.

An undirected graph $G = (V, E)$ is connected if for every pair of vertices $u, v \in V$ , there exists a sequence of edges (a walk) in $E$ linking $u$ to $v$ . Equivalently, $G$ has exactly one connected component.

How It Works

To determine whether a graph is connected, pick any vertex and perform a search — breadth-first search (BFS) or depth-first search (DFS) — marking each vertex you visit. If every vertex in the graph gets marked, the graph is connected. If some vertices remain unvisited, the graph is disconnected, and each maximal set of mutually reachable vertices forms a connected component.

Example

Problem: Determine whether the graph G with vertices {A, B, C, D} and edges {AB, BC, CD} is connected.

Step 1: Start at vertex A. From A, edge AB lets us reach B.

A \to B

Step 2: From B, edge BC lets us reach C. From C, edge CD lets us reach D.

A \to B \to C \to D

Step 3: All four vertices {A, B, C, D} have been visited from a single starting vertex, so every pair is connected by a path.

Answer: G is a connected graph because every vertex is reachable from every other vertex.

Why It Matters

Connectivity is a prerequisite for many graph algorithms and theorems. Spanning trees, Euler circuits, and network flow problems all require — or begin by checking — that the graph is connected. In computer science and engineering, verifying connectivity models whether a communication network can transmit data between any two nodes.

Common Mistakes

Mistake: Confusing connected with complete. Students sometimes think a connected graph must have an edge between every pair of vertices.

Correction: A connected graph only needs a path (possibly through intermediate vertices) between each pair. A complete graph has a direct edge between every pair — a much stronger condition.