Name of the edge whose removal causes the graph to be weakly connected

Question

Given a strongly connected digraph G, there exists an edge that, when removed, makes the graph weakly connected. What is this edge called?

Answer 1

The terminology here is a bit awkward.

Let's compare this to the undirected setting, where:

• An edge cut $[X,\overline X]$ is the set of all edges between $X$ and its complement;
• In a connected graph, deleting the edges in an edge cut disconnects the graph, and every set of edges whose deletion disconnects the graph contains an edge cut.
• When an edge cut consists of only one edge, it is called a cut edge or bridge.

In the case of directed graphs:

• A directed edge cut, also sometimes denoted $[X,\overline X]$, is the set of all edges from $X$ to its complement;
• In a strongly connected graph, deleting the edges in a directed edge cut results in a graph that is no longer strongly connected, and every set of edges whose deletion does this contains a directed edge cut.
• When a directed edge cut consists of only one edge, we... don't actually have special terminology for that.

It would be reasonable to call this a "directed cut edge" or a "directed bridge", but these are not actually accepted terminology, and these are sometimes used for cut edges/bridges in the undirected sense. (That is, for edges in a weakly connected directed graph which stop it from being weakly connected.)

In a formal write-up relying on this notion, it would be fine to define such an edge to be a "directed bridge", but I wouldn't use the term without giving the definition. The only way I can see to avoid such a term is to talk about a "directed edge cut of size 1".

---

P.S. It is inaccurate to say that deleting the edge makes the graph weakly connected. All strongly connected graphs are already weakly connected. Deleting an edge $(x,y)$ can turn a strongly connected graph into a graph that is no longer strongly connected, but is still weakly connected. (It takes some work to show that a strongly connected graph cannot stop being weakly connected after the deletion of one edge, but that is in fact true.)