2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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... $\endgroup$
    – JMoravitz
    Commented Jan 22, 2018 at 3:23
  • 1
    $\begingroup$ Sorry. Of course, I mean graphs which are connected. I forgot to write it down. I fixed it. $\endgroup$
    – Hamed
    Commented Jan 22, 2018 at 3:26
  • $\begingroup$ Can the graph be infinite? $\endgroup$ Commented Jan 22, 2018 at 3:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Commented Jan 22, 2018 at 3:34
  • $\begingroup$ I added finiteness too. Thanks. $\endgroup$
    – Hamed
    Commented Jan 22, 2018 at 3:37

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ OK. I see your point. Let me think about it for a minute. $\endgroup$ Commented Jan 22, 2018 at 4:27
  • 1
    $\begingroup$ The proof should be fixed now. $\endgroup$ Commented Jan 22, 2018 at 5:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .