I am reading graph theroy. Here author mentions that the number of possible digraphs is truly huge. Each of the $V^2$ possible directed edges (including self-loops) could be present or not, so the total number of graphs is $2^{V^2}$. For undirected graphs the number is given by $2^{V(V+1)/2}$.

For $V =2$ we have $8$ undirected graphs and $16$ digraphs.

My question , can any write all combinations for $V =2$ asuming vertices are $"a" $and $"b"$. I tried but not able to find all. For example in directed $\emptyset$, ${a}, {(a,a)}, {(b,b)}, {b}, {(a,b)}, {(b,a)}, {(a,b), (b,a)} $I came up with 8, but according to formula above we should get 16


Here are them:

  • without loops:

$\emptyset$, $\{(a,b)\}$, $\{(b,a)\}$, $\{(a,b),(b,a)\}$

  • with $(a,a)$ loop but without $(b, b)$ loop:

$\{(a,a)\}$, $\{(a,a), (a,b)\}$, $\{(a,a), (b,a)\}$, $\{(a,a), (a,b), (b,a)\}$

  • with $(b,b)$ loop but without $(a,a)$ loop

this case is symmetric with the second case

  • with both $(a,a)$ and $(b,b)$ loops

$\{(a,a),(b,b)\}$, $\{(a,a),(b,b),(a,b)\}$, $\{(a,a),(b,b),(b,a)\}$, $\{(a,a),(b,b),(a,b),(b,a)\}$

Can you observe how other three cases relate to the first case?

  • $\begingroup$ Yes. We are combining loop to first case. By the way for your time and answer. $\endgroup$ – venkysmarty Jun 23 '15 at 14:08

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.