# Thread: how many orientations does a simple graph g have?

1. ## how many orientations does a simple graph g have?

hi

I'm stuck on the followinq question

How many orientations does a simple graph g have?

for one vertex there is one, just the isolated vertex

for two vertices there are 3, i think...two isolated vertices u and v, a digraph with arc uv and a digraph with arc vu.

i'm not sure where to go from here

thanks for your help

2. ## Check definition of "simple" graph

Your description of your calculation already lets you count how many directed graphs there are. Between each pair of points, there seem to be 3 possibilities - no edge, an edge directed one way, an edge directed the other. You can count how many pairs of points there are - n choose 2 - points. So you've counted
$\displaystyle 3 ^ { \binom{n}{2} }$
graphs.

However there is another definition of simple graph that doesn't allow for directed vertices. If so, your calculation overcounts because there's only 2 possibilities - no edge, or yes, there's an edge.

3. hi, i just want to check i understand

i'm working from the definition of a simple graph which states that g contains no loops or multiple edges, so i don't think i need to worry about overcounting

i understand now that i need to divide into the three cases for each pair of vertices

using your formula i get

n number of orientations
1 1
2 3
3 9
4 24
....

are these values correct?

thanks again for your help

4. ## Definition of simple graph

I'm still not sure if you're working with simple graphs or simple directed graphs. The definition I'm getting from the web for simple graph is: "unweighted, undirected" graph. Please note the "undirected"!

The formula is not being interpreted correctly. The
$\displaystyle \binom {n}{m} = \frac {n!}{m!(n-m)!}$

so the first few values are:
$\displaystyle \binom {2}{2} = 1, \implies 3^{\binom{2}{2}} = 3$
$\displaystyle \binom {3}{2} = 3, \implies 3^{\binom{3}{2}} = 27$
$\displaystyle \binom {4}{2} = 6, \implies 3^{\binom{4}{2}} = 729$

5. I need the graphs to be directed since i'm looking for the number of orientations.

i think that if i have 3 vertices and and a directed edge (arc) between 1 pair i count this once not 6 times for alternate direction and the choice of the two other pairs.

this means that for n=1,2,3,4,5,.... i get 1,2,7,42,582

(this sequence is from wolfram mathworld)

im trying to find the formula for this sequence, does anyone know it?

thank you

,

,

,

,

,

,

# howmany orientation does a simple graph G have

Click on a term to search for related topics.