Is it possible to have more than one complete directed graphs? And if yes, how many? I found a formula but I can't make sense of it.

35 Views Asked by At

3Cn2 = 3[num of arcs in undirected graph for some reason]

Is the formula I found relating to this, I would imagine it means for every node you can either have an arc pointing to it, from it, or both ways, hence the 3, then I have no Idea why they wouldn't use

n*(n-1)

being the num of arcs in a directed graph.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $n=2$ and call the points $A$ and $B$. An undirected complete graph has $\frac 12\cdot 2 \cdot 1=1$ edge. The text points out that you have $3=3^1=3^{2 \choose 2}$ complete directed graphs where it allows one edge from $A$ to $B$ alone, one edge from $B$ to $A$ alone, or one edge in each direction. You are thinking you need to start with two edges, one in each direction. The choices of whether to retain the two edges are not independent. If you use your exponent you get $3^2=9$ different graphs, but I can't find that many.