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!
[Math] Maximum number of edges in a directed graph on $n$ vertices without cycles
directed graphsgraph theory
Related Solutions
The maximum number of cycles is infinity (if you allow cycles that repeat edges; and if you have at least 1 cycle).
Suppose any vertex of the graph has degree $4$ or more. Then there are at least $\binom 42 = 6$ edges connecting its neighbors; including any of those edges would create a triangle. So at least $6$ edges must be missing in this case, and the number of edges in the graph is at most $9$.
On the other hand, suppose all vertices have degree at most $3$. The sum of degrees in a graph is twice the number of edges, by the handshaking lemma, so the number of edges in this case is at most $\frac12(3+3+3+3+3+3) = 9$.
Since one of these must be the case, $9$ is a universal upper bound. As @PJK points out in the comments, in the second case, we can achieve $9$ by making a $3$-regular graph with no triangles:
We can also think of this graph as the complete bipartite graph $K_{3,3}$.
It is not a coincidence that the complete bipartite graph is the graph with the maximum number of edges here: Mantel's theorem says that for $n$ vertices, the maximum number of edges in a triangle-free graph is achieved by the balanced or nearly-balanced complete bipartite graph $K_{\lfloor n/2\rfloor, \lceil n/2 \rceil}$.
Best Answer
The question is equivalent to
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<b$. 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.