3
$\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$
2
  • $\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
    Commented Mar 9, 2017 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
    Commented Mar 9, 2017 at 7:07

2 Answers 2

3
$\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$
1
  • 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
    Commented Mar 9, 2017 at 8:24
2
$\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$

You must log in to answer this question.

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