# 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.

• Are you talking about very specifically a graph which is connected in the first place? Because otherwise, take any zero-regular graph on multiple vertices, or take the disjoint union of two separate triangles ($K_3$)'s which would be a one-regular graph on six vertices with there being no path from any vertex in the one triangle to the other... Commented Jan 22, 2018 at 3:23
• Sorry. Of course, I mean graphs which are connected. I forgot to write it down. I fixed it. Commented Jan 22, 2018 at 3:26
• Can the graph be infinite? Commented Jan 22, 2018 at 3:34
• You should also specify that the graph be finite. Otherwise, the integers as treated as a $1$-regular digraph with directed edge from $a$ to $b$ iff $a+1=b$ would be another counterexample as every directed path only ever goes up but not down. Commented Jan 22, 2018 at 3:34
• I added finiteness too. Thanks. Commented Jan 22, 2018 at 3:37

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$.