What is the maximum number of edges in a directed graph with n nodes

Question

What is the maximum number of edges in a directed graph with n nodes  Is there any upper bound

User · Answer

Directed graph   Question  What s the maximum number of edges in a directed graph with n vertices    Assume there are no self-loops  Assume there there is at most one edge from a given start vertex to a given end vertex       Each edge is specified by its start vertex and end vertex  There are n   choices for the start vertex  Since there are no self-loops  there are   n-1 choices for the end vertex  Multiplying these together counts all   possible choices    Answer  n n-1   Undirected graph  Question  What s the maximum number of edges in an undirected graph with n vertices    Assume there are no self-loops  Assume there there is at most one edge from a given start vertex to a given end vertex       In an undirected graph  each edge is specified by its two endpoints   and order doesn t matter  The number of edges is therefore the number   of subsets of size 2 chosen from the set of vertices  Since the set of   vertices has size n  the number of such subsets is given by the   binomial coefficient C n 2   also known as  n choose 2    Using the   formula for binomial coefficients  C n 2    n n-1  2    Answer   n  n-1   2

User · Answer

In an undirected graph  excluding multigraphs   the answer is n  n-1  2   In a directed graph an edge may occur in both directions between two nodes  then the answer is n  n-1

User · Answer

The correct answer is n  n-1  2  Each edge has been counted twice  hence the division by 2  A complete graph has the maximum number of edges  which is given by n choose 2   n  n-1  2

User · Answer

There can be as many as n n-1  2 edges in the graph if not multi-edge is allowed   And this is achievable if we label the vertices 1 2     n and there s an edge from i to j iff i gt j   See here

User · Answer

In the graph with self loop   max edges  n n   such as we have 4 nodes vertex   4 nodes   16 edges  4 4

User · Answer

If you have N nodes  there are N - 1 directed edges than can lead from it  going to every other node   Therefore  the maximum number of edges is N    N - 1

User · Answer

Putting it another way    A complete graph is an undirected graph where each distinct pair of vertices has an unique edge connecting them  This is intuitive in the sense that  you are basically choosing 2 vertices from a collection of n vertices    nC2   n   n-2   2    n n-1  2   This is the maximum number of edges an undirected graph can have  Now  for directed graph  each edge converts into two directed edges  So just multiply the previous result with two  That gives you the result  n n-1

User · Answer

In a directed graph having N vertices  each vertex can connect to N-1 other vertices in the graph Assuming  no self loop   Hence  the total number of edges can be are N N-1

User · Answer

Can also be thought of as the number of ways of choosing pairs of nodes n choose 2   n n-1  2  True if only any pair can have only one edge  Multiply by 2 otherwise

User · Answer

If the graph is not a multi graph then it is clearly n    n - 1   as each node can at most have edges to every other node  If this is a multigraph  then there is no max limit

User · Answer

In addition to the intuitive explanation Chris Smith has provided  we can consider why this is the case from a different perspective  considering undirected graphs    To see why in a DIRECTED graph the answer is n  n-1   consider an undirected graph  which simply means that if there is a link between two nodes  A and B  then you can go in both ways  from A to B and from B to A   The maximum number of edges in an undirected graph is n n-1  2 and obviously in a directed graph there are twice as many   Good  you might ask  but why are there a maximum of n n-1  2 edges in an undirected graph  For that  Consider n points  nodes  and ask how many edges can one make from the first point  Obviously  n-1 edges  Now how many edges can one draw from the second point  given that you connected the first point  Since the first and the second point are already connected  there are n-2 edges that can be done  And so on  So the sum of all edges is   Sum    n-1   n-2   n-3      3 2 1    Since there are  n-1  terms in the Sum  and the average of Sum in such a series is   n-1  1  2   last   first  2   Sum   n n-1  2

User · Answer

Undirected is N 2  Simple - every node has N options of edges  himself included   total of N nodes thus N N

[algorithm] What is the maximum number of edges in a directed graph with n nodes?

Directed graph:

Undirected graph

Examples related to algorithm

Examples related to math

Examples related to graph

Examples related to max