# cycles of nodes in random graph theory

• November 20th 2012, 04:57 AM
xaosman
cycles of nodes in random graph theory
Could someone help me out with some basic graph theory?

(a cycle consisting of four nodes connected by four links to a cycle. A cycle has no start or end point nor a direction.)

I want to show that in the random graph G(n, p) (where n is the number of nodes nodes and p is the probability of the existence of a link between two nodes), that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4 (consisting of only 4 nodes that is)

I know from examples that there are (1/6)n(n -2)(n -1) possible triangles from n number of nodes. But when I use the same method for the number of connected nodes with length 4 I get:

(from n choose 4) = (1/24)n(n -3)(n -2)(n -1)

Which is not correct and I would need to multiply it with 3 to make it right and I don't get why. could someone help me out?

I'm so sorry if anything is unclear. English is not my frist language.
• November 20th 2012, 06:36 AM
Plato
Re: cycles of nodes in random graph theory
Quote:

Originally Posted by xaosman
I want to show that in the random graph G(n, p) (where n is the number of nodes nodes and p is the probability of the existence of a link between two nodes), that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4 (consisting of only 4 nodes that is)
(from n choose 4) = (1/24)n(n -3)(n -2)(n -1)
Which is not correct and I would need to multiply it with 3 to make it right and I don't get why. could someone help me out?

Where did you get this "that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4"

Clearly it should be $\binom{n}{4}=\frac{n(n-1)(n-2)(n-3)}{4!}$.

There must be other restrictions you have not included.