[Math] Strongly connected graph: equivalent formulation

graph theory

A digraph(=directed graph = graph with directed/oriented edges) $X$ is said to be strongly connected if for any distinct vertices $v,w$, there is a directed path from $v$ to $w$.

In particular in such digraphs, every vertex has an incoming edge and an outgoing edge. My question is, whether the last property characterizes strongly connected digraphs? To be precise,

Q. Let $X$ be a connected, finite, digraph. Assume that every vertex has at least one incoming and one outgoing edge. Is $X$ strongly connected?

Best Answer

It is easy to see that having indegree, outdegree $\ge 1$ for every vertex is a necessary condition for a graph to be strongly connected. Otherwise, you would have an unreachable vertex or a vertex from which there are no paths.

But it is not a sufficient condition; counterexample below.

Draw two directed triangle graphs and join them by a single directed edge. enter image description here

Since the degrees are not balanced, there is a directed path from one strongly connected component to the other, but not the other way around; despite the underlying undirected graph being connected.