2
$\begingroup$

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,

Q. Let $X$ be a connected, finite, digraph. Assume that every vertex has at least one incoming and one outgoing edge. Is $X$ strongly connected?

$\endgroup$
  • $\begingroup$ I presume we make the usual assumptions about simple graphs? No multi-edges and no self-loops? Also, when you say "characterize", it means if and only if, correct? $\endgroup$ – Akay Mar 9 '17 at 6:43
  • 1
    $\begingroup$ yes; let us exclude graphs without loops. But, there can be single edge from $v$ to $w$ and also from $w$ to $v$; since they have different orientations, these are not actually multiple edges. (In characterize, it is certainly if and only if, and one direction I mentioned follows from definition of strongly connected graph; other direction is in question.) $\endgroup$ – p Groups Mar 9 '17 at 7:07
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$
2
$\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. enter image description here

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$
  • 2
    $\begingroup$ On the other hand, a sufficient condition for a (finite) connected digraph to be stronly connected is that every vertex have the same number of incoming as outgoing edges. And, of course, a necessary and sufficient condition is that every set of vertices, except the empty set and the set of all vertices, have at least one outgoing edge. $\endgroup$ – bof Mar 9 '17 at 8:24
  • $\begingroup$ Hmm..the second condition is interesting. I was not aware of that. Isn't it also required that each such set have an incoming edge too? Edit: I see that it is implied. :) $\endgroup$ – Akay Mar 9 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.