I have an issue with a question below.
In the Erdős–Rényi model on 4 vertices with p=0.5, calculate the probability that the graph is bipartite.
As far as I know we have 4^3 = 64 possible graphs. But how to calculate probability that graph is bipartite.
Thank you, in advance.
Best Answer
With only $4$ vertices, the number of possibilities is limited, so there's many ways to count all the bipartite graphs. Then, divide by $2^6 = 64$ to get the probability. (Here, $6 = \binom 42$ is the total number of possible edges: the number of edges in the complete graph $K_4$.)
It is useful to remember that a graph is bipartite if and only if it has no odd cycles. With $4$ vertices, the only possible odd cycle is $C_3$.
If you have $0$, $1$, or $2$ edges, there cannot be any odd cycles, so there are $\binom 60 + \binom 61 + \binom 62$ cases here.
If you have $3$ edges, not all $\binom 63$ cases work; the graph might be $C_3$ plus an isolated vertex. How many cases must we rule out?
If you have $4$ edges, only a few cases work: the only bipartite graph on $4$ vertices and $4$ edges up to isomorphism is $K_{2,2} = C_4$. How many ways are there to get $C_4$?
With $5$ and $6$ edges, there are no bipartite graphs to speak of.
Another reasonable approach is to use the inclusion-exclusion principle on the four possible $3$-cycles that could appear in the graph, to find the probability that none of them appear.