CODEWITHSUNDEEP
graphdirected-acyclic-graphs
panjiangwei
panjiangwei

Reputation: 163

How many edges can there be in a DAG?

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

Upvotes: 16

Views: 24332

Answers (1)

Richard Sitze
Richard Sitze

Reputation: 8463

Assume N vertices/nodes, and let's explore building up a DAG with maximum edges. Consider any given node, say N1. The maximum # of nodes it can point to, or edges, at this early stage is N-1. Let's choose a second node N2: it can point to all nodes except itself and N1 - that's N-2 additional edges. Continue for remaining nodes, each can point to one less edge than the node before. The last node can point to 0 other nodes.

Sum of all edges: (N-1) + (N-2) + .. + 1 + 0 == (N-1)(N)/2

Upvotes: 30

Related Questions