Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even isomorphic graphs also.
Counting the number of directed graphs with $N$ vertices and $E$ edges?
3
$\begingroup$
combinatorics
graph-theory
discrete-mathematics
binomial-coefficients
1 Answers
3
If you treat isomorphic graphs separately, then one way to think about this is as follows. If you start off with $N$ nodes and want $E$ edges, you could build a graph by considering an $E$-element subset of the set of all possible edges in the graph. The number of possible edges is $N^2$, since each node can be connected to each other node (including itself), so the number of ways you can pick $E$ of these edges is $\binom{N^2}{E}$. This is
$ \frac{(N^2)!}{(E!) \cdot (N^2 - E)!}, $
which is a staggeringly huge number.
Hope this helps!