# Strongly connected graph: equivalent formulation

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?

• 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? – Akay Mar 9 '17 at 6:43
• 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.) – p Groups Mar 9 '17 at 7:07

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