Suppose we construct a complete bipartite graph on n labeled

Suppose we construct a complete bipartite graph on n labeled vertices by flipping a fair coin to decide whether each vertex should be in vertex set V₁ or vertex set V₂. Once we have decided the vertex sets, we connect every vertex in V₁ to every vertex in V₂, and do not add any edges between vertices of V₁ or between vertices of V₂. What is the expected number of edges in a complete bipartite graph constructed in this way? Use linearity of expectation to calculate your answer.

Solution

Back-up Theory

Expected value = Number x probability

Solution

Since probability on flipping a coin is 1/2 each, probabilty a vertex will be in V1 = 1/2 = probabilty a vertex will be in V2.

Again, there are n vertices, hence Expected number of vertices in V1 = n x (1/2) = n/2. Similarly, Expected number of vertices in V2 = n x (1/2) = n/2.

Since each vertex in V1 is connected to each vertex in V2, Expected number of edges in the graph

= (n/2) x (n/2) = n²/4 ANSWER