What is the maximum number of edges in a directed

Question

What is the maximum number of edges in a directed graph with n nodes? Is there any upper bound?

Answer 1

Can also be thought of as the number of ways of choosing pairs of nodes n choose 2 = n(n-1)/2. True if only any pair can have only one edge. Multiply by 2 otherwise

Answer 2

There can be as many as n(n-1)/2 edges in the graph if not multi-edge is allowed.

And this is achievable if we label the vertices 1,2,...,n and there's an edge from i to j iff i>j.

See here.

Answer 3

In an undirected graph (excluding multigraphs), the answer is n*(n-1)/2. In a directed graph an edge may occur in both directions between two nodes, then the answer is n*(n-1).

Answer 4

In addition to the intuitive explanation Chris Smith has provided, we can consider why this is the case from a different perspective: considering undirected graphs.

To see why in a DIRECTED graph the answer is n*(n-1), consider an undirected graph (which simply means that if there is a link between two nodes (A and B) then you can go in both ways: from A to B and from B to A). The maximum number of edges in an undirected graph is n(n-1)/2 and obviously in a directed graph there are twice as many.

Good, you might ask, but why are there a maximum of n(n-1)/2 edges in an undirected graph? For that, Consider n points (nodes) and ask how many edges can one make from the first point. Obviously, n-1 edges. Now how many edges can one draw from the second point, given that you connected the first point? Since the first and the second point are already connected, there are n-2 edges that can be done. And so on. So the sum of all edges is:

Sum = (n-1)+(n-2)+(n-3)+...+3+2+1 

Since there are (n-1) terms in the Sum, and the average of Sum in such a series is ((n-1)+1)/2 {(last + first)/2}, Sum = n(n-1)/2

Answer 5

In a directed graph having N vertices, each vertex can connect to N-1 other vertices in the graph(Assuming, no self loop). Hence, the total number of edges can be are N(N-1).