 Connected graph

An undirected graph is connected when every pair $u,v$ of vertices is joined by a finite graph path. The length-zero graph path consisting of $u$ alone is allowed, so a single-vertex graph is connected. We use the term here for nonempty graphs; conventions for the graph with no vertices vary. Adjacent vertices are connected, but connected vertices need not be adjacent: in our six-vertex example, $A$ reaches $F$ along $A,C,D,F$, although $AF$ is absent.

Allowing walks instead of graph paths gives the same test for a connected graph. Whenever a finite walk revisits a vertex, delete the intervening closed portion; repeating this leaves a graph path with the same endpoints. This simple shortening argument explains why revisiting locations cannot help decide reachability.^[ref]

Connectivity can conceal fragile connections. Removing $CD$ from our graph produces two connected components of a graph, on $\{A,B,C\}$ and $\{D,E,F\}$: $CD$ is a bridge in a graph. Removing $AB$ instead preserves connectivity, because $A,C,B$ supplies an alternative graph path. If edges represent communication links, this calculation says precisely which single link failure separates the two groups. It is a conclusion about this model, independent of the lengths in its drawing.

A tree is a nonempty connected graph without a graph cycle; equivalently, each pair of vertices has exactly one graph path between them. Delete $BC$ and $EF$ from our example. The remaining edgesform a spanning tree: all six vertices remain, with $6-1=5$ edges. The graph path $A,C,D,F$ is now unique, and every remaining edge is a bridge in a graph. Adding $BC$ back creates exactly one graph cycle, $B,A,C,B$. Thus graph cycles express alternative routes, while a tree retains just enough connections for reachability. More generally, a finite connected graph on $n\ge 1$ vertices has at least $n-1$ edges, with equality exactly for a tree. One proof repeatedly removes an edge on a graph cycle, preserving connectivity, until a spanning tree remains.^[ref]

For a finite graph, breadth-first search tests connectivity by starting at one vertex and discovering neighbours in successive layers. Starting at $A$, the layers in our example are $\{A\}$, $\{B,C\}$, $\{D\}$, $\{E,F\}$. Every vertex is discovered, and the layer numbers give graph distances from $A$. Recording one discovery edge for each new vertex constructs a spanning tree. This turns an existence question into both a concrete route and a certificate of connectivity.