Given any relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly connected.
With that said is there a simple way to prove for all $n,m\in\mathbb{Z}$ such that $2\leq n\leq m\leq 2n−2$ there always exist at least one minimally strong digraph with $n$ vertices and $m$ arcs?
When $2\leq m=n$ we can construct a cycle with $n$ vertices which is minimally strong and has $m$ arcs whereas if we have $2\leq m=2n-2$ we can take a tree graph with $n$ vertices and replace each edge $\{u,v\}$ with the arcs $(u,v)$ and $(v,u)$ to similarly get a minimally strong digraph with exactly $m$ arcs and $n$ vertices. But what if $n<m< 2n-2$? How can I find a clean way to prove this in general?
Best Answer
If $n<m<2n-2$, write $$m=2(m-n)+(2n-m)\,.$$ We see that $2n-m\geq 3$. Now construct an oriented cycle $C$ on $2n-m$ vertices. Form a tree using one vertex of $C$ and the remaining $m-n\geq 1$ vertices. Then the digraph is minimally strong, and it has exactly $n$ vertices and $m$ arcs.