A directed graph is weakly connected if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph.
We know that for an undirected connected graph with $n$ vertices and $m$ edges, if $m\ge n$, then the graph must contain a cycle. Now, for a weakly connected directed graph, is there a similar result? Obviously, in this case, having $m=n$ (where $m$ is the number of arcs and $n$ is the number of vertices) is not sufficient to guarantee the existence of cycles. This is because a cycle in an underlying graph may not necessarily form a directed cycle.
- What is the minimum number of arcs in a directed graph with $n$ vertices to guarantee
the existence of at least one directed cycle? - Does there always exist a directed cycle in an $n$-vertex (where n is relatively large) complete digraph with a simple underlying graph?
Best Answer
You need ${n \choose 2} +1 $ arcs for $n\ge 2$, for $n=1$ you need one arc. That assumes the redundant arcs (going from the same vertex to the same vertex) don't exist), as this will clearly allow any number of redundant arcs without a cycle.
To show that ${n \choose 2}$ are not enough, take the graph on the vertex set $\{1,\ldots,n\}$ and arcs go from $i$ to $j$ exactly when $i < j$. That graph is weakly connected and has ${n \choose 2}$ arcs, but no cycle.
If you do have ${n \choose 2} +1$ arcs, then there either is a loop (so a cycle itself), or there are 2 vertices that have 2 arcs connecting them. Because redunant arcs were excluded, those 2 arcs must be in opposite directions, creating a cycle.