# Finding the count of triangles in a 4 vertices complete graph after coin toss/erasure

Consider a complete graph with 4 vertices (i.e., every two vertices are connected by an edge). For each of the 6 edges we toss a coin, and if heads occur, then we erase the edge. Let X be the number of triangles in the graph. Find E(X).

How should I even approach this?

Thanks!

## 2 Answers

P(0 edges removed) = 1/(2^6) = 1/64. Number of triangles = 4.

P(1 edge removed) = 6/64. Number of triangles = 2.

P(2 edges removed) = 15/64 (from 6 choose 2). Number of triangles (if they share a vertex) = 1. P(share vertex) = 12/15 (12 combinations from the 15 pairs of edges). Number of triangles (if they don't share a vertex) = 0.

P(3 edges removed) = 20/64. Number of triangles (if they all shared 1 vertex) = 1. P(share vertex) = 4/20 (4 combinations from the 20 triplets of edges). Otherwise = 0.

E(number of triangles) = 4*1/64 + 2*6/64 + 1*12/15*15/64 + 1*4/20*20/64 = 32/64.

E(number of triangles) = 0.5.

Each potential triangle has probability $\frac{1}{8}$ of being an actual triangle after the flips, so contributes $\frac{1}{8}$ to the expected number of triangles.

There are $\binom{4}{3}$ potential triangles.

Adding the expectations for each potential triangle, it follows that the expected number of triangles is $${\small{\binom{4}{3}}}\left({\small{\frac{1}{8}}}\right)={\small{\frac{1}{2}}}$$

• can you please explain how you got the probability 1/8 for each potential triangle? and why there are 4 choose 3 potential triangles, when there are 4 triangles in the original graph(small size) and 4 more triangles (with two smaller in each) ? – Lola1984 Nov 5 '17 at 3:01
• Firstly, in a complete graph with $4$ vertices, any $3$ vertices determine a triangle. There are no other triangles (i.e., no "smaller triangles"). So there are only $4$ triangles before the flips. – quasi Nov 5 '17 at 3:03
• Each potential triangle has $3$ edges, so the probability that it remains a triangle after the flips is $$\left({\small{\frac{1}{2}}}\right)^3 = {\small{\frac{1}{8}}}$$ – quasi Nov 5 '17 at 3:05
• Thank you, I wasn't aware of this and this definitely cleared things up~ – Lola1984 Nov 5 '17 at 3:19