2
$\begingroup$

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?

$\endgroup$

migrated from cs.stackexchange.com Apr 30 '16 at 2:19

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

  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 30 '16 at 2:18
  • $\begingroup$ Ah, I see. My deepest apologies. Thank you for migrating my question to the appropriate forum for me. $\endgroup$ – user50420 Apr 30 '16 at 3:17
4
$\begingroup$

Every Directed Acyclic Graph (DAG) on $n$ vertices with the most edges possible is isomorphic to a graph like this:

enter image description here

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.

$\endgroup$
  • $\begingroup$ So if I wanted to figure out how many more edges I could add to a pre-existing DAG, I'd just find out what the maximum possible number of edges is and subtract the number of existing edges from that. This answer has been extremely useful to me as a beginner to the concept of graphs! $\endgroup$ – user50420 Apr 30 '16 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.