Why is the number of orientations of order $n$ equal to $3^\binom{n}{2}$?

38 Views Asked by At

I read that in West's Introduction to Graph Theory, but no proof was provided. I get that there are $\binom{n}{2}$ edges in a graph, but I have no clue where the $3$ comes in.

1

There are 1 best solutions below

0
On BEST ANSWER

There are $3$ possible orientations for each edge of an oriented graph: forward arrow, reverse arrow, and no arrow. So $3^\binom{n}{2}$ is the total number of orientations. If you are only counting tournaments, then the orientation of "no arrow" is not valid, so the answer would be $2^\binom{n}{2}$