5
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ Have you tried induction? $\endgroup$ Dec 4 '17 at 1:03
  • $\begingroup$ I would try induction if I knew how to treat a graph with n vertices... unfortunately I don't $\endgroup$
    – Lola1984
    Dec 4 '17 at 1:18
  • 1
    $\begingroup$ 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 $\endgroup$ Dec 4 '17 at 1:22
  • $\begingroup$ thanks, but then in this case I am completely confused and have no idea how to do it lol, any suggestions? $\endgroup$
    – Lola1984
    Dec 4 '17 at 1:34
9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.