The existence and identification of strongly connected edge direction assignments in bridgeless graphs and multigraphs

Abstract

The aim of this paper is two-fold. First, we will provide clarity on a result concerning the strong connectivity, a concept whose usefulness is readily apparent in several fields of study including social networking and transport networks, of a bridgeless connected graph achieved through the depth-first search (DFS) technique. To this end, we will demonstrate two rigorous mathematical proofs of this robust and well-known result. One proof takes the approach of seeking a contradiction by investigating the relationship between directed paths and maximal strongly connected subgraphs after the application of DFS. The other proof features a direct approach that demonstrates that for each tree edge $\{U,V\}$, there is a directed path from $V$ to $U$ by utilizing the fact that each edge in a connected multigraph on at least two vertices is either a bridge or is included in some cycle. Second, for a multigraph without a bridge, we provide two different proofs ensuring the existence of an assignment of edge directions that induces strong connectivity. One of these proofs utilizes the previous fact, whereas the second proof is independent of it and features a technique that focuses on collapsing entire connected multigraphs into a single vertex.