Disconnected Graph — Definition, Formula & Examples

A disconnected graph is a graph in which at least one pair of vertices has no path connecting them. In other words, the graph breaks into two or more separate pieces, called connected components.

A graph $G = (V, E)$ is disconnected if there exist vertices $u, v \in V$ such that no walk (and therefore no path) exists from $u$ to $v$ . Equivalently, $G$ is disconnected if it has more than one connected component.

How It Works

To determine whether a graph is disconnected, pick any vertex and find all vertices reachable from it using BFS or DFS. If some vertices remain unvisited, the graph is disconnected. Each maximal set of mutually reachable vertices forms a connected component. A graph with

n

vertices and no edges at all is disconnected (assuming

n \geq 2

) and has

n

connected components.

Worked Example

Problem: Consider a graph G with vertex set V = {1, 2, 3, 4, 5} and edge set E = {(1,2), (2,3), (4,5)}. Is G connected or disconnected? How many connected components does it have?

Step 1: Starting from vertex 1, traverse reachable vertices. Vertex 1 connects to 2, and vertex 2 connects to 3. So {1, 2, 3} are mutually reachable.

Step 2: Vertices 4 and 5 are connected to each other but not to any vertex in {1, 2, 3}. So {4, 5} forms a separate group.

Step 3: Since no path exists from vertex 1 to vertex 4 (for example), the graph is disconnected. The connected components are {1, 2, 3} and {4, 5}.

Answer: G is a disconnected graph with 2 connected components: {1, 2, 3} and {4, 5}.

Why It Matters

Disconnected graphs model real situations where a network has isolated clusters, such as separate groups in a social network or unreachable nodes in a computer network. Identifying connected components is a fundamental step in algorithms for network analysis, circuit design, and clustering problems in data science.

Common Mistakes

Mistake: Confusing a disconnected graph with a graph that simply has a vertex of degree zero (an isolated vertex).

Correction: An isolated vertex is one way a graph can be disconnected, but a graph can also be disconnected without any isolated vertices — it just needs two or more components, each of which may have edges internally.