Skip to content

Connected Network

Definition

An undirected network is connected if every pair of vertices can be joined by a path. It is disconnected if at least one pair cannot be joined.

Interpretation

A network is connected when it is in one piece: from any vertex one can reach any other along edges. The spanning-tree and undirected routing problems in the course assume this of the network.

Two networks of five vertices: one in which every pair is joined by a path, and one split into two parts with no edge between them.

Both networks have the same five vertices. On the left every pair is joined by a path, for example A−B−DA-B-D or A−C−EA-C-E. On the right the edges stay within {A,B,C}\{A,B,C\} or within {D,E}\{D,E\}, so no path joins AA to DD; one such pair already makes the network disconnected, although no vertex is isolated.

The condition matters whenever a route or a tree must cover the whole network: a disconnected network has no spanning tree, and vertices in different parts have no shortest path between them.

Key Results

  • A disconnected network has no spanning tree covering all its vertices.
  • A tree is connected as well as cycle-free.
  • For a directed flow network, available directed routes must still be checked; undirected connectedness alone does not imply flow to the sink.

Examples

  • A chain of roads linking A to B and B to C connects all three towns.
  • Two groups of towns with no road between the groups are disconnected.

Prerequisites

Sources

Aliases: connected graph

Last updated: 20 October 2026 03:02