Is there an example of a finite regular (weakly) connected digraph which is not strongly connected? I came across this question in my research. Couldn't think of an answer, or find an answer anywhere. > Is there an example of a finite (weakly) connected regular digraph which is not strongly connected? By (weakly) connected digraph $D$, I mean the underlying undirected graph is connected. A digraph $D$ is strongly connected if any vertex is reachable from any other vertex. By a $d$-regular digraph, I mean a digraph $D$, such that every vertex $x$ has $d$ arcs going out of $x$ and $d$ arcs coming into $x$. Also, we allow the possibility of both parallel arcs and loops (loop is understood as an arc going both in and out) and also parallel loops.

Suppose $G = (V,E)$ is a finite, weakly connected, $d$-regular directed graph. Since $G$ is weakly connected, any cut that separates $V$ into two non-empty subsets is crossed by at least one edge.

The number of edges that cross said cut in each direction must be the same, or else $G$ wouldn't be finite and regular. In particular, there is at least one edge in each direction.

If there are vertices $u$ and $v$ such that there is no path in $G$ from $u$ to $v$, there must be a cut in $G$ such that $u$ and $v$ are on opposite sides of the cut and there is no edge of $G$ crossing from $u$'s side to $v$'s side.

But $d$-regularity means that there is no edge across that cut in the opposite direction either, contradicting the weak connectedness of $G$.