Define what a path permits
A graph models a chosen relationship through vertices and edges. An undirected edge can be traversed both ways; a directed edge must be followed in its stated direction. Decide which model applies before discussing connectivity. A physical cable does not by itself establish that one application may reach another. Edges could instead represent permissions, roads, or dependencies. Here connectivity concerns existence of paths, not their minimum weight or delay. One available route does not establish that the route meets a capacity target or deadline. Those additional properties require further information and possibly a different algorithm.
Partition an undirected graph
An undirected graph is connected when every pair of vertices has a path between them. Otherwise it decomposes into connected components. With A–B–C and D–E but no edges between those groups, the components are {A,B,C} and {D,E}. An isolated vertex F forms another component rather than disappearing from the classification. A zero-length path allows a vertex to reach itself. Reachability in an undirected graph is an equivalence relation, so components partition the vertices. This explains both complete coverage and the impossibility of two distinct components overlapping only partially.
Find components with graph search
Starting BFS or DFS from one vertex identifies all vertices reachable from it. In an undirected graph this set is its connected component. Repeat from each still-unvisited vertex to enumerate every component. With adjacency lists and suitable visited bookkeeping, the complete traversal takes O(V+E) time. An adjacency matrix can require a different amount of work because discovering neighbors scans a whole row. State the representation alongside the complexity claim. Marking visited vertices at the appropriate point prevents repeated expansion. The theorem concerns this implemented traversal strategy, not every program that happens to contain a queue or recursive search.
Strong connectivity requires both directions
In the directed chain A→B→C, A reaches C but C cannot reach A. The vertices do not form one strongly connected component; each belongs to its own. Adding C→A makes all three mutually reachable. Weak connectivity instead asks whether the graph becomes connected when directions are ignored. The original chain is weakly connected but not strongly connected. Reaching every vertex from a single starting point therefore does not prove strong connectivity. Trace the required direction in every claim. Algorithms for strongly connected components use additional structure beyond treating a directed traversal’s first reachable set as an ordinary undirected component.
Connectivity is not fault tolerance
A currently connected graph can become disconnected when one edge disappears. Such an edge is a bridge. Both edges in A–B–C are bridges, whereas adding A–C creates a triangle with an alternative route after any single edge removal. Correlated failures can still invalidate that simple model when several edges depend on one physical device. Distinguish being connected now, having redundant graph routes, and having independent failure domains. Real communication also includes permissions, name resolution, direction, and changes over time. A connectivity calculation is evidence about the specified graph, not an unconditional guarantee of service availability.
Count isolated vertices
Building vertices only from an edge list can omit isolated vertices that never appear in any edge. Register the specified vertex set before adding edges. Verify a component result by checking that each vertex is assigned exactly once and that no edge joins two reported undirected components. These checks complement traversal tests: a correct BFS over an incomplete input representation still produces an incomplete classification of the intended graph.