Random Graph

A random graph is a graph in which properties such as the number of graph vertices, graph edges, and connections between them are determined in some random way. The graphs illustrated above are random graphs on 10 vertices with edge probabilities distributed uniformly in .

Erdős and Rényi (1960) showed that for many monotone-increasing graph properties of random graphs, graphs of a size slightly less than a certain threshold are very unlikely to have the property, whereas graphs with a few more graph edges are almost certain to have it. This is known as a phase transition (Janson et al. 2000, p. 103). Almost all graphs are connected and nonplanar (Skiena 1990, p. 156).

Pósa (1976) used the Pósa rotation-extension technique to show that, for a sufficiently large constant , almost all graphs with edges have a Hamiltonian cycle.

The Wolfram Language command RandomGraph[n, m] gives a pseudorandom graph with vertices and edges.

He et al. (2026) reported bulk spectral universality for uniformly random simple -regular graphs, for every fixed integer . As through admissible values with even, the local eigenvalue statistics of the adjacency matrix, rescaled by the local spectral density at any fixed bulk energy, converge to the sine process associated with the Gaussian orthogonal ensemble. The result also includes consecutive-gap and fixed-energy correlation universality (He et al. 2026).

He et al. (2026) state that GPT-6 assisted proof development at the level of a coauthor, with the authors responsible for the entire paper.

For the model , sampled uniformly from the simple graphs on labeled vertices with edges, Coja-Oghlan et al. (2026) determined two consecutive possible values of the chromatic number when and . Let solve . Then is either or with high probability, where is the ceiling function. More precisely, put and choose as in their theorem. The first value occurs with high probability whenever is not an integer and is outside

where the union is over integers .

For a sparse binomial random graph, Lin and Yang (2026) determined the minimum number of paths needed to partition its edges. If and , then with high probability has a decomposition into exactly nonempty simple paths, where counts its odd-degree vertices. Every such decomposition needs at least this many paths, since each odd-degree graph vertex must be an endpoint of a path. Here denotes little-o notation.

For every fixed , the adjacency matrix of a graph sampled from is nonsingular with probability at least for a constant (Liang et al. 2026). This follows from their exponential rank bound for real symmetric random matrices.