Can two strongly connected components be connected with a directed edge and still be strongly connected?

Question

In a directed graph with strongly connected components such as this graph, adding a directed edge wouldn't it make the strongly connected components no longer be strongly connected?

Like in this graph after insertion of edge.

Answer 1

Yes!

The easiest way to define strongly connected components for a graph is to start with an equivalence relation called strong connectedness on the vertices $V$ of a graph. Given two vertices $u,v \in V$, write $u \sim v$ if there is a both a directed path from $u$ to $v$ and a directed path from $v$ to $u$ (including the case where $u=v$ via paths of length zero). We say such $u$ and $v$ are strongly connected. This is an equivalence relation since it is:

1. Reflexive: For all $v \in V$, $v \sim v$.
2. Symmetric: For all $u, v \in V$, $u \sim v \Longleftrightarrow v \sim u$ (this is also rather tautological).
3. Transitive: For all $u,v,w \in V$, if $u \sim v$ and $v \sim w$ then $u \sim w$. This follows by composition of paths.

Now it is a standard fact that equivalence relations on a set partition that set into equivalence classes, which is the coarsest partition such that in each partitioned set, all the elements are equivalent. In other words, in this context, we break the set of vertices up into the “largest possible” pieces such that within every piece, every vertex has a path to every other vertex and vice versa.

Now it is possible for there to be a directed edge between two separate strongly connected components in a graph. For instance, if we begin with two completely separate components and add edges from component $A$ to component $B$, there will still be no paths in the other direction, from any vertex in component $B$ to any vertex in component $A$, so we will not have $a \sim b$ for any $a \in A, b \in B$ --- thus, the components $A$ and $B$ are not "collapsed" into one giant component. (On the other hand, adding edges both ways between $A$ and $B$ will strongly connect every vertex $A$ to every vertex of $B$; they will collapse into one component).