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

algorithm math graph max
Loolooii picture Loolooii · Feb 20, 2011 · Viewed 141.2k times · Source

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

Answer

Chris Smith picture Chris Smith · Feb 20, 2011

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

Related questions

Choosing an attractive linear scale for a graph's Y Axis

I'm writing a bit of code to display a bar (or line) graph in our software. Everything's going fine. The thing that's got me stumped is labeling the Y axis. The caller can tell me how finely they want the …

Read More
Calculate distance between two latitude-longitude points? (Haversine formula)

How do I calculate the distance between two points specified by latitude and longitude? For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to understand the relative accuracies of the approaches available.

Read More
Unfamiliar symbol in algorithm: what does ∀ mean?

I'm reading about an algorithm (it's a path-finding algorithm based on A*), and it contains a mathematical symbol I'm unfamiliar with: ∀ Here is the context: v(s) ≥ g(s) = mins'∈pred(s)(v(s') + c(s', s)) ∀s ≠ sstart Can …

Read More