A graph consists of a set of vertices, denoted by V, and a set of edges, denoted by E. E is defined over V.

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.