How many more edges can be added to a graph while keeping it acyclic? If I have a connected, directed graph with $n$ vertices and $m$ edges, is there some sort of formula that describes how many more edges can be added to the graph while keeping it acyclic?
 A: Every Directed Acyclic Graph (DAG) on $n$ vertices with the most edges possible is isomorphic to a graph like this:

Let $f(n)$ denote the most edges that a DAG $G=(V,E)$ on $n$ vertices can have.
Claim: We have that $$f(n)=\frac{n(n-1)}{2}.$$ Moreover, any DAG on $n$ vertices with $f(n)$ edges is isomorphic to the following graph: 
$$V^*(n) = 1,\ldots,n,$$ 
$$E^*(n) = \{(i,j)\ \mid \ j>i,\quad i,j \in [n]\}.$$ 
Finally, every DAG on $n$ vertices with less that $f(n)$ edges can be augmented to have $f(n)$ edges and remain a DAG.
Remark: $\frac{n(n-1)}{2}$ is the number of edges is a complete undirected graph and is thus an obvious upper bound on the number of edges in a DAG, since to have more requires a digon (a directed cycle of length two). The claim gives a specific orientation of a complete undirected graph to make the directed graph acyclic.
Proof sketch: Every DAG can have its vertices topologically ordered, i.e. there is a mapping from $V$ to $1,...,|V|$, so that after mapping the vertices all edges in graph are of the form $(i,j)$ for $i<j$. Consider the first vertex in a topological ordering of a DAG. It can point to all $n-1$ other vertices. The next vertex can only point to at most $n-2$ vertices, and so on. In total, a DAG with the most possible edges will thus have:
$$ (n-1) + (n-2) + \ldots + 2 + 1 = \frac{n (n-1)}{2}$$ edges. Any DAG with less edges can be augmented to have this many edges by topologically sorting its vertices and then adding in all missing edges from vertex $i$ to $j$ where $i < j$ in the topological ordering. 
