Maximum number of edges in a directed graph on $n$ vertices without cycles 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!
 A: 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.
A: Parcly's answer is correct. Just to explain this in a different way, the maximum value of (in-degree + out-degree) for every node in the graph has to be n-1. If it was any more than n-1, then there is one node which is in both the in-degree and out-degree implying a cycle. Therefore each node than can have n-1 edges adjacent on it and so the maximum number of edges in the graph is n(n−1)/2. The division by 2 is necessary to account for the double counting.
A: If you had a 3x3 DAG, 4x4 DAG, and 5x5 DAG with maximum number of edges they could have, they would look like 
[[0 1 1]      [[0 1 1 1]      [[0 1 1 1 1]
 [0 0 1]       [0 0 1 1]       [0 0 1 1 1]
 [0 0 0]]      [0 0 0 1]       [0 0 0 1 1]
               [0 0 0 0]]      [0 0 0 0 1]
                               [0 0 0 0 0]]

The first thing I thought of was that the number of 1's in the DAG matched the triangle numbers pattern, which is given by $\frac{n(n+1)}{2}$, where $n$ is the number of nodes. However, that would be true if there were 1's along the diagonal (self-loops). Since there aren't self-loops (DAG), then you have to subtract $n$ from the triangle numbers sequence $\frac{n(n+1)}{2} - n$, which gives you the maximum number of edges a DAG can have as $\frac{n(n-1)}{2}$, again $n$ = # of nodes.
