# Connectedness in Directed Graphs

Suppose $G$ is a directed graph on $n$ vertices where all in-degrees and our-degrees are constant $d \geq 2$ (though the adjacency matrix need not be symmetric). Suppose further that the graph is strongly connected.

Since the graph is strongly connected, for any two vertices $v$ and $w$, there is a directed path connecting $v$ to $w$. I am curious about a different kind of path which isn't unidirectional, but "alternating" in a sense.

That is, is there a path $$v, u_1, u_2, u_3, \dots, u_{2t-1}, w$$ where $(u_1 \to v)$ is a directed edge, but $(u_1 \to u_2)$ is a directed edges, $(u_3 \to u_2)$ is a directed edge, $(u_3 \to u_4)$ is a directed edge, and so on. That is, $u_{2m-1}$ has two directed edges to $u_{2m-2}$ and $u_{2m}$.

So this is a kind of path between $v$ and $w$, but where the directions alternate in a sense.

My question: Is there always such a path connecting any two vertices of the directed graph $G$ which is strongly connected? If not, what properties are necessary for such a result to hold?

P.S. $G$ is not a directed cycle. Thanks to the comment for pointing that out.

• In a cycle, every vertex has $d=1$ and the graph is obviously strongly connected. There is no "alternating" path, though. – Fabio Somenzi May 18 '18 at 15:16
• @FabioSomenzi True, thats a trivial case which can be ignored. I have updated the question accordingly. – BharatRam May 18 '18 at 15:22
• Directed cycle is not just a trivial example, but more like the most basic counterexample, in particular for any graph $G$ you can make $G' \supset G$ that does not have this property by adding some version/modification of a directed cycle to $G$. – dtldarek May 18 '18 at 15:30

Consider the following strongly connected digraph with $d=3$ and the problem of finding an alternating path from vertex $0$ to vertex $3$.
Such a path must eventually use either edge $(0,2)$ or edge $(3,1)$. Let's call these two edges "bridges." All paths from $0$ back to itself that cross a bridge have even length and all similarly constrained paths from $0$ to $1$ have odd length. Hence no matter what alternating path is followed, it can never cross a bridge; hence it cannot connect $0$ to $3$.
EDIT: There is also a counterexample with $d=2$:
From vertex $0$, alternating paths cannot reach vertex $2$.