In an undirected random graph of 8 vertices, the probability of an edge appearing between a pair of vertices is 1/2. What is the expected number of unordered cycles of length 3?
Here's how I thought about it:
Method 1 Basically the loops ("unordered", I assume that the vertices can be taken in any order) of length 3 will be triangles.
Let the number of vertices = v, and none of these cycles be 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's start from the outer edge, and triangles with it can be based. For the first edge we select (two vertices), there are (n-2) other vertices to select the third point of the triangle. So, (n-2) in the first term.
Further, the last term is that the very last side that we choose to base our triangles would have left and right triangles, taken already on the first side that we have chosen, and its closest predecessor.
The average term is a product of the remaining number of edges and possible triangles.
.--------. . . . . . .
With the above set of 8 vertices, you can trivially think about it visually. (If you need better diagrams, I will do it!). Thus, for v = 8, C (8) = 40. Thus, in probability, the edges 1/2.,.
Method 2 The number of triangles of n points is nC3, where C is a "combination". But since half of these ribs will not exist.,
I am not sure how to proceed beyond this point. Any hints in the right direction would be wonderful. By the way, this is not a matter of homework.