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

• Have you tried induction? Dec 4 '17 at 1:03
• I would try induction if I knew how to treat a graph with n vertices... unfortunately I don't Dec 4 '17 at 1:18
• If it was an undirected graph, the answer would be $n-1$. For a directed graph, you can definitely fit more edges. a simple counterexample is a triangle with two of the edges directed clockwise and one counterclockwise. This has no cycles and $n=33$ vertices and $3$ edges, more than $n-1=2$ edges. So, you won't be able to prove that it's $n-1$, because it's not $n-1$ ... :P Dec 4 '17 at 1:22
• thanks, but then in this case I am completely confused and have no idea how to do it lol, any suggestions? Dec 4 '17 at 1:34

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. 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.

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.

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.