How many edges can be in a DAG?

In a directed acyclic graph with n vertices, what is the maximum possible number of directed edges in it?

+5
source share
1 answer

Assume N vertices / nodes, and study creating DAGs with max edges. Consider any given node, say, N1. The maximum number of nodes it can point to or edges at this early stage is N-1. Let's choose the second node N2: it can point to all nodes except itself, and N1 - to N-2 additional edges. Continue for the remaining nodes, each of them may point to one smaller edge than the node before. The last node can point to 0 other nodes.

The sum of all the edges: (N-1) + (N-2) + .. + 1 + 0 == (N-1) (N) / 2

+13
source

All Articles