What is the maximum number of edges in a directed graph with n nodes? [closed]

Solution 1:

If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is N * (N - 1).

Solution 2:

Directed graph:

Question: What's the maximum number of edges in a directed graph with n vertices?

• Assume there are no self-loops.
• Assume there there is at most one edge from a given start vertex to a given end vertex.

Each edge is specified by its start vertex and end vertex. There are n choices for the start vertex. Since there are no self-loops, there are n-1 choices for the end vertex. Multiplying these together counts all possible choices.

Answer: n(n−1)

Undirected graph

Question: What's the maximum number of edges in an undirected graph with n vertices?

• Assume there are no self-loops.
• Assume there there is at most one edge from a given start vertex to a given end vertex.

In an undirected graph, each edge is specified by its two endpoints and order doesn't matter. The number of edges is therefore the number of subsets of size 2 chosen from the set of vertices. Since the set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2) (also known as "n choose 2"). Using the formula for binomial coefficients, C(n,2) = n(n-1)/2.

Answer: (n*(n-1))/2

Solution 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).