How many arcs are required to guarantee the existence of cycles?

Question

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?

Answer 1

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.

Answer 2

In a directed graph, to guarantee the existence of at least one directed cycle, you need to have at least n + 1 arcs, where n is the number of vertices.

Here's why:

Consider a directed graph with n vertices and n arcs. The maximum number of vertices you can include without forming a cycle is n, and you can do this by arranging the vertices in a line or path, where each vertex points to the next one. This forms a directed acyclic graph, also known as a DAG.

But as soon as you add one more arc (n + 1 arcs total), you're forced to connect an already connected vertex to another vertex, forming a directed cycle. So, the minimum number of arcs needed to guarantee the existence of a directed cycle is n + 1.

Regarding your second question, in a complete digraph with n vertices (where n is relatively large), there will always exist a directed cycle, regardless of the underlying graph being simple.

A complete digraph is a directed graph in which every pair of different vertices is connected by a pair of unique edges (one in each direction). Due to this property, you can start from any vertex and follow the directed edges to return to the starting vertex, forming a directed cycle. This holds true regardless of how large n is, as long as it's greater than or equal to 3 (since you can't have a directed cycle with less than 3 vertices).