Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 36 2 a Solution Created 2026-10-03 Updated 2026-10-14
Write . A disconnected graph has a connected component of a graph of size . For a fixed -element vertex set , all edges between and its complement must be absent. Their independent absence has probability . The union bound givesSet . Since is fixed in , . For large , the final sum is at most the geometric series , which tends to zero. Hence the binomial random graph is connected with probability tending to one, as in connectivity of a fixed-density binomial random graph.