[Math] Is it possible to predict number of edges in a strongly connected directed graph

graph theory

I know that

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 question is

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 attempt is

1) is impossible because we need cycles in a directed graph to make it strongly connected. (Just a gut feeling that I am failing to articulate into actual logic)

2) is simply $2(n-1)$ (Just a gut feeling that I am failing to articulate into actual logic)

Best Answer

  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.

Related Question