Fix , , and with . A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most , with high probability. The expected value and variance of the isolated vertex count concentrate it around . A Cayley formula upper bound for connected sets excludes component sizes through a small fixed fraction of ; the empty-graph cut bound excludes the remaining sizes up to . An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is , where . The Markov inequality completes the count of vertices outside the unique large graph component.

Articles by others on the same topic (0)

There are currently no matching articles.