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>.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec13.pdf[MIT, Connectivity and Trees, Theorem 1]{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 <edges>
$$
\{AB,AC,CD,DE,DF\}
$$
form 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\geq1$ <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.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>{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.


 Connected graph (source code)