Editing Component (graph theory) (section)

== In random graphs ==
{{main|Giant component}}
[[File:Critical 1000-vertex Erdős–Rényi–Gilbert graph.svg|thumb|An [[Erdős–Rényi model|Erdős–Rényi–Gilbert random graph]] with 1000 vertices with edge probability <math>p=1/(n-1)</math> (in the critical range), showing a large component and many small ones]]
In [[random graph]]s the sizes of components are given by a [[random variable]], which, in turn, depends on the specific model of how random graphs are chosen. 
In the <math>G(n, p)</math> version of the [[Erdős–Rényi model|Erdős–Rényi–Gilbert model]], a graph on <math>n</math> vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with {{nowrap|probability <math>p</math>}} of including an edge and probability <math>1-p</math> of leaving those two vertices without an edge connecting them.{{r|frikar}} The connectivity of this model depends {{nowrap|on <math>p</math>,}} and there are three different ranges {{nowrap|of <math>p</math>}} with very different behavior from each other. In the analysis below, all outcomes occur [[with high probability]], meaning that the probability of the outcome is arbitrarily close to one for sufficiently large values {{nowrap|of <math>n</math>.}} The analysis depends on a parameter <math>\varepsilon</math>, a positive constant independent of <math>n</math> that can be arbitrarily close to zero.

;Subcritical <math>p < (1-\varepsilon)/n</math>
: In this range of <math>p</math>, all components are simple and very small. The largest component has logarithmic size. The graph is a [[pseudoforest]]. Most of its components are trees: the number of vertices in components that have cycles grows more slowly than any unbounded function of the number of vertices. Every tree of fixed size occurs linearly many times.{{r|subcritical}}
;Critical <math>p \approx 1/n</math>
: The largest connected component has a number of vertices proportional to {{nowrap|<math>n^{2/3}</math>.}} There may exist several other large components; however, the total number of vertices in non-tree components is again proportional to {{nowrap|<math>n^{2/3}</math>.{{r|critical}}}}
;Supercritical <math>p >(1+\varepsilon)/n</math>
: There is a single [[giant component]] containing a linear number of vertices. For large values of <math>p</math> its size approaches the whole graph: <math>|C_1| \approx yn</math> where <math>y</math> is the positive solution to the equation {{nowrap|<math>e^{-p n y }=1-y</math>.}} The remaining components are small, with logarithmic size.{{r|supercritical}}
In the same model of random graphs, there will exist multiple connected components with high probability for values of <math>p</math> below a significantly higher threshold, {{nowrap|<math>p<(1-\varepsilon)(\log n)/n</math>,}} and a single connected component for values above the threshold, {{nowrap|<math>p>(1+\varepsilon)(\log n)/n</math>.}} This phenomenon is closely related to the [[coupon collector's problem]]: in order to be connected, a random graph needs enough edges for each vertex to be incident to at least one edge. More precisely, if random edges are added one by one to a graph, then with high probability the first edge whose addition connects the whole graph touches the last isolated vertex.{{r|random-connectivity}}

For different models including the random subgraphs of grid graphs, the connected components are described by [[percolation theory]]. A key question in this theory is the existence of a [[percolation threshold]], a critical probability above which a giant component (or infinite component) exists and below which it does not.{{r|cohav}}