Maximum number of edges in a directed graph on $n$ vertices without cycles

Question

What is the maximum number of edges in a directed graph with $n$ vertices (which has no cycles). Logically it should be $n-1$, however I don't know how to prove this...

Any help would be appreciated, Thanks!

Answer 1

The question is equivalent to

What is the maximum size (edge count) of a directed acyclic graph?

It is easy to see that $\frac{n(n-1)}{2}$ edges is possible for $n$ vertices – realised by a tournament where the vertices are numbered $1,\dots,n$ and an edge runs from $a$ to $b$ iff $a<b$. Having more than $\frac{n(n-1)}{2}$ edges is not possible because there would then be at least one pair of vertices with two edges, thus a cycle, between them, so this number is the maximum.