# 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?

## migrated from cs.stackexchange.comApr 30 '16 at 2:19

This question came from our site for students, researchers and practitioners of computer science.

• This sounds like a pure math question. While CS.SE doesn't have a strict prohibition against math questions if there's some reason why they are best answered from a CS perspective, we expect the question to articulate the connection to CS and explain why the question needs to be answered from CS perspective. That doesn't seem to apply here, so I will migrate this to Math.SE, where it seems more suitable. – D.W. Apr 30 '16 at 2:18
• Ah, I see. My deepest apologies. Thank you for migrating my question to the appropriate forum for me. – user50420 Apr 30 '16 at 3:17

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.