each pair of vertices whether to include an edge connecting that pair, with of including an edge and probability of leaving those two vertices without an edge connecting them. The connectivity of this model depends and there are three different ranges 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 The analysis depends on a parameter , a positive constant independent of that can be arbitrarily close to zero. Subcritical In this range of , 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. Critical The largest connected component has a number of vertices proportional to There may exist several other large components; however, the total number of vertices in non-tree components is again proportional to Supercritical There is a single giant component containing a linear number of vertices. For large values of its size approaches the whole graph: where is the positive solution to the equation The remaining components are small, with logarithmic size. In the same model of random graphs, there will exist multiple connected components with high probability for values of below a significantly higher threshold, and a single connected component for values above the threshold, 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. 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. References External links MATLAB code to find components in undirected graphs, MATLAB File Exchange. Connected components, Steven Skiena, The Stony Brook Algorithm Repository Graph connectivity Graph theory objects