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,
$\endgroup$ 2Q. Let $X$ be a connected, finite, digraph. Assume that every vertex has at least one incoming and one outgoing edge. Is $X$ strongly connected?
2 Answers
$\begingroup$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.
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.
$\endgroup$ 1 $\begingroup$No, for example take a digraph on six vertices $u,v,w,x,y,z$. If the edges are $(u,v),(v,w),(w,u),(x,y),(y,z),(z,x),(u,x),(v,y),(w,z)$ then this is connected and every vertex has at least one incoming and at least one outgoing edge. But there is no directed path from any of $x,y,z$ to any of $u,v,w$.
$\endgroup$
