How many directed graphs are possible using V vertices

directed graphsgraph theory

As an example, if I have 2 vertices V1, V2.
All the possible directed graphs ( there can be indegree 0 vertices as well) are 3 {{V1,V2}, {V1->V2}, {V1<-V2}}.
But, when there are 3 vertices all the possible graphs are found to be very large.
{{V1,V2,V3}, {V1->V2,V3}, {V1<-V2,V3}…..{V1->V2->V3} …. } . Like

  1. graphs with edges 0
  2. graphs with 1 edges and their directionality changed
  3. graphs with 2 edges and their directionality changed
  4. graphs with 3 edges and there directionality changed

My attempt so far: As mentioned above I simply analyze the questions, but it is found to be growing larger. I was able to found that for any N no. of vertices, all the possible edges ( undirected ) are N*(N-1) /2. It is like I have to analyze all the number of possible edges and their directionality.

But, which is not clear is the possible number of graphs is growing with a possible number of edges.
I would appreciate any suggestions on how to obtain all the possible directed graphs from N number of vertices.

Best Answer

There are $\binom{V}{2}=V(V-1)/2$ distincy pairs of vertices. For any pair of vertices $\{u,v\}$, any one of the 3 options can hold:

  1. Either there is no edge between $u$ and $v$
  2. There is an edge directed from $u$ to $v$
  3. There is an edge directed from $v$ to $u$

Hence total number of directed graphs on $V$ vertices is $3^{V(V-1)/2}$.

Related Question