What is the minimum number of edges in a strongly connected digraph on $n$ vertices?
At first I thought it would be $n(n-1)$ but that is not the minimum number of edges. I would be glad if someone could help me with this.
[Math] Edges in strongly connected digraph
combinatoricsgraph theory
Best Answer
The minimum number is $n$, because you can create a cycle with them that connects all the $n$ vertices in one strongly-connected component. With fewer than $n$ edges, you get at most a tree.