Is it possible to predict number of edges in a strongly connected directed graph?

Question

I know the following:

A graph that is complete and undirected with $n$ nodes will have $n(n-1)/2$ edges

A graph that is complete and directed with $n$ nodes will have $n(n-1)$ edges

A graph that is connected (without cycles) and undirected with $n$ nodes will have $(n-1)$ edges

My questions are:

1. A graph that is strongly connected (without cycles) and directed with $n$ nodes will have $?$ edges

2. A graph that is strongly connected (with cycles) and directed with $n$ nodes will have $?$ edges

I am not sure about the last two. Could someone help shed some light and provide an analytic form for them as well as provide an explanation why this is the case?

My attempts are:

1. The answer is impossible because we need cycles in a directed graph to make it strongly connected. (This is a gut feeling that I am failing to articulate into actual formal mathematical reasoning)

2. The answer is simply $2(n-1)$. (This is a gut feeling that I am failing to articulate into actual formal mathematical reasoning)

Answer 1

1. Your gut feeling is right:

   • A cycle is a sequence $v_1, v_2, ... v_k$ of vertices such that: $v_1 = v_k$, and there is a directed edge between $v_i$ and $v_{i+1}$ for $i \in [1, k-2]$.

   • A graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex. In particular, $v_2$ is reachable from $v_1$ and $v_1$ is reachable from $v_2$, which means that there is a cycle in the graph.

2. A (directed) cycle graph with $n$ vertices and $n$ edges is strongly connected. Conversely, any graph with $n-1$ edges is not strongly connected. Furthermore, the complete graph is strongly connected. So a strongly connected graph with $n$ nodes will have between $n$ and $n(n-1)$ edges.