0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}}}$$

$\endgroup$
4
  • $\begingroup$ 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) ? $\endgroup$ – Lola1984 Nov 5 '17 at 3:01
  • $\begingroup$ 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. $\endgroup$ – quasi Nov 5 '17 at 3:03
  • $\begingroup$ 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}}}$$ $\endgroup$ – quasi Nov 5 '17 at 3:05
  • $\begingroup$ Thank you, I wasn't aware of this and this definitely cleared things up~ $\endgroup$ – Lola1984 Nov 5 '17 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.