Number of cycles in a random graph

Question

In an undirected random graph of 8 vertices, the probability of an edge being present between a pair of vertices in 1/2. What is the expected number of unordered cycles of length 3?

Here's how I thought of going about it:

Method 1 Basically cycles ("unordered" i am assuming to mean that the vertices can be taken in any order) of length 3 would be triangles.

Letting number of vertices = v, and no of such cycles being C

For n=3, C = 1

For n = 4, c = 4. (a square with 2 diagonal lines. 4 unique triangles). ....

For n>3, C(n) = (n-2) + (n-2)(n-3) + (n-4), generalizing.

This is because: let us start with an outside edge, and the triangles possible with that as a base. For the first edge we choose (2 vertices gone there), there are (n-2) other vertices to choose the 3rd point of triangle. So (n-2) in the first term.

Next, the last term is because the very last side we choose to base our triangles on would have its leftmost and rightmost triangles taken already by the first side we chose and its immediate predecessor.

The middle term is the product of the remaining number of edges and possible triangles.

      .--------.

.                   .


.                   .

      .        .

With the above set of 8 vertices one can trivially think it out visually. (If better diagrams are needed, I shall do the needful!). So for v=8, C(8) = 40. So, as probability of an edge is 1/2 . . .

Method 2 The number of triangles from n points is nC3, where C is "combination". But as half of these edges are not expected to exist . . .

I am not sure how to proceed beyond this point. Any hints in the right direction would be great. Btw its not a homework question.

Answer 1

You have nC3 possible triangles. For a triangle to appear all three edges must exist - so the probability of a specific triangle to appear is 1/8.

The expected number of triangles is then (nC3) / 8.

In your case, 8C3 / 8 or 7.