Section 5: Connectivity and Components

What does it mean for a graph to be connected?

A graph is connected if there is a path between every pair of vertices.

What is a connected component?

A connected component is a maximal group of connected vertices — a part of the graph where every vertex can reach every other vertex in that group.

What is a cut vertex?

A cut vertex is one whose removal increases the number of connected components.
💡 Visual: Like removing a bridge that splits an island into two parts.

What is a bridge in a graph?

A bridge (or cut edge) is an edge whose removal disconnects part of the graph.

What is a strongly connected directed graph?

In a directed graph, it’s one where every vertex can reach every other vertex by following the directions of edges.

What is a weakly connected directed graph?

If replacing all directed edges with undirected ones makes the graph connected, it’s weakly connected.