1
$\begingroup$

A digraph $G = G(V,E)$ on the set of vertices $V$ is a graph where every edge $e ∈ E$ is directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on $n$ vertices are there?

Can someone help me start this question because I have no idea. I am trying to think how many possible graphs there can be with $n$ vertices but I don't know how many there can be because how can you know what the maximum possible edges there can be with $n$ vertices?

EDIT: Just read a definition that for complete graphs $K_n$ there are $n\choose2$ edges. So the number of possible graphs on $n$ vertices is basically the number of ways to choose a set of edges from a maximum of $n\choose2$ edges.

Let $E=${$e_1,...,e_{n\choose2}$}. So the number of subsets of this is $2^{n\choose2}$ which is the number of graphs on $n$ vertices right?

$\endgroup$
1
$\begingroup$

The number of (labelled, loop-free) undirected graphs is $2^{\binom{n}{2}}$ because for each of the $\binom{n}{2}$ pairs of distinct vertices $u$ and $v$ we choose between (a) adding an edge between $u$ and $v$, or (b) not adding an edge between $u$ and $v$.

Hint: Now for (labelled, loop-free) digraphs, we choose between (a) adding an edge from $u$ to $v$, (b) adding an edge from $v$ to $u$, or (c) not adding an edge between $u$ and $v$.

$\endgroup$
  • $\begingroup$ At least I got the first part right. I still have no idea after reading your hint... $\endgroup$ – snowman Jan 31 '15 at 14:06
  • $\begingroup$ Can someone help me a bit more please $\endgroup$ – snowman Jan 31 '15 at 16:28

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.