Definition:Connected (Graph Theory)

This page is about connectedness in graph theory. For other uses, see Definition:Connected.

Definition

Vertices

Two vertices $u, v \in G$ are connected iff either:

• $u = v$
• $u \ne v$, and there exists a walk between them.

Graph

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

Otherwise, it is called disconnected.

Also see

• $k$-Connected

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$