|
A random graph is based a set of n vertices. The edges are created according to a random rule, usually a edge exists between 2 vertices u and v with a 50% probability.
The set of all random graphs is the set of all graphs on n vertices.
If the number of random graphs with a property P divided by the number of random graphs tends to 1 as n tends to infinity, then it is said that almost all graphs have the property P.
For example, almost all graphs contain C_n, a cycle with n edges. This is seen by counting the number of graphs on n vertices that have this property.
|