Suppose I have a directed acyclic graph (DAG) $G=(V,E)$, how many ways can I add a single edge and still have a DAG?
I saw a similar question here whose solution uses a topological order on the vertices. I thought to count (somehow) the number of edges that could be potentially added while preserving the order. However since the ordering may not be unique you'd have to enumerate over all possible orderings whilst making sure to not count pendent edges twice. But perhaps there's a better way, ideally a closed expression?
Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. I'll assume that you'd like to know how many directed edges we can add, so that if for $u,v \in V$ we can add either of $uv$ and $vu$, we count that as two ways of adding a new edge. Otherwise, the answer is ${n \choose 2} - m$, since for any pair of non-neighbouring vertices $u,v$, you can add at least one of $uv$ and $vu$ to the graph (e.g. if in a topological ordering $u$ comes before $v$, then you can add $uv$).
Now for any pair of vertices $u,v$, if you can't add the edge $uv$ to the graph, that's either because $uv$ is already an edge, or because adding $uv$ would create a directed cycle, which happens precisely if $u$ is reachable from $v$. Since $G$ is a DAG, these two possibilities are mutually exclusive. This means that if $m'$ denotes the number of ordered pairs $(u,v)$ such that $u$ is reachable from $v$, then the number of directed edges you can add is $n(n-1) - m - m'$. Note that $m'$ is the number of edges of the transitive closure of $G$.