Question

Is it always possible to make an undirected graph with two connected components connected by adding a single edge?

• Why or why not? (Proof or counter example) [if true, give a proof, if false, give counter example]
• Does the same hold true for directed graphs (and strongly connected components rather than connected components)? (Proof or counter example) [if true, give a proof, if false, give counter example]

Answer 1

Connected components in undirected graphs

A connected component of an undirected graph G = (V, E) is a maximal set of vertices S ⊂ V such that for each u ∈ S and v ∈ S, there exists a path in G from vertex u to vertex v.

Definition (Formal Definition)

Let u ∼ v if and only if G has a path from vertex u to vertex v. This is an equivalence relation (it is symmetric, reflexive, and transitive). Then, a connected component of G is an equivalence class of this relation ∼. Recall that the equivalence class of a vertex u over a relation ∼ is the set of all vertices v such that u ∼ v.

Algorithm to find connected components in a undirected graph

In order to find a connected component of an undirected graph, we can just pick a vertex and start doing a search (BFS or DFS) from that vertex. All the vertices we can reach from that vertex compose a single connected component. To find all the connected components, then, we just need to go through every vertex, finding their connected components one at a time by searching the graph. Note however that we do not need to search from a vertex v if we have already found it to be part of a previous connected component. Hence, if we keep track of what vertices we have already encountered, we will only need to perform one BFS for each connected component.

Proof.

When searching from a particular vertex v,

we will clearly never reach any nodes outside the connected component with DFS or BFS. So we just need to prove that we will in fact reach all connected vertices.

We can prove this by induction:

Consider the vertices at minimum distance i from vertex v.

Call these vertices “level i” vertices.

If BFS or DFS succesfully reaches all vertices at level i, then they must reach all vertices at level i + 1, since each veriex at distance i + 1 from v must be connected to some vertex at distance i from v.

This is the inductive step, and for the base case, DFS or BFS will clearly reach all vertices at level 0 (just v itself).

So indeed this algorithm will find each connected component correctly.

The searches in the above algorithm take total time O(|E|+|V |),

because each BFS or DFS call takes linear time in the number of edges and vertices for its component, and each component is only searched once, so all searches will take time linear in the total number of edges and vertices.

Connectivity in directed graphs

How can we extend the notion of connected components to directed graphs?

Definition (Strongly connected component (SCC))

A strongly connected component in a directed graph G = (V, E) is a maximal set of vertices S ⊂ V such that each vertex v ∈ S has a path to each other vertex u ∈ S. This is the same as the definition using equivalence classes for undirected graphs, except now u ∼ v if and only if there is a path from u to v AND a path from v to u.

Definition (Weakly connected component)

Let G = (V, E) be a directed graph, and let G0 be the undirected graph that is formed by replacing each directed edge of G with an undirected edge. Then the weakly connected components of G are exactly the connected components of G0 .

Input:

a directed graph G = (V, E), in adjacency list representation. Assume that the vertices V are labeled 1, 2, 3, . . . , n.

1. Let Grev denote the graph G after the orientation of all arcs have been reversed.

2. Run the DFS-Loop subroutine on Grev, processing vertices in any arbitrary order, to obtain a finishing time f(v) for each vertex v ∈ V .

3. Run the DFS-Loop subroutine on G, processing vertices in decreasing order of f(v), to assign a “leader” to each vertex v ∈ V . The leader of a vertex v will be the source vertex that the DFS that discovered v started from.

4. The strongly connected components of G correspond to vertices of G that share a common leader.

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.