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 [0,1].
Erdős and Rényi (1960) showed that for many monotone-increasing 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).
The Wolfram Language command RandomGraph [{n, m}] gives a pseudorandom graph with n vertices and m edges.
See also
Graph, Graph Theory, Phase TransitionExplore with Wolfram|Alpha
More things to try:
References
Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.Bollobás, B. Random Graphs. London: Academic Press, 1985.Erdős, P. and Rényi, A. "On the Evolution of Random Graphs." Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61, 1960.Erdős, P. and Spencer, J. Probabilistic Methods in Combinatorics. New York: Academic Press, 1974.Janson, S.; Łuczak, T.; and Ruciński, A. Random Graphs. New York: Wiley, 2000.Kolchin, V. F. Random Graphs. New York: Cambridge University Press, 1998.Newman, M. E. J. Strogatz, S. H.; and Watts, D. J. "Random Graphs with Arbitrary Degree Distributions and Their Applications. Phys. Rev. E 64, 026118, 2001.Palmer, E. M. Graphical Evolution: An Introduction to the Theory of Random Graphs. New York: Wiley, 1985.Skiena, S. "Random Graphs." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 154-160, 1990.Steele, J. M. "Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees." Prob. Eng. Inform. Sci. 1, 47-59, 1987.Referenced on Wolfram|Alpha
Random GraphCite this as:
Weisstein, Eric W. "Random Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RandomGraph.html