information:highlighting
Classification of graphs

Several authors have provided additional conditions that classify some graphs as being of class one or class two, but do not provide a complete classification. For instance, if the vertices of the maximum degree Δ in a graph G form an independent set, or more generally if the induced subgraph for this set of vertices is a forest, then G must be of class one.

Erdős & Wilson (1977) showed that almost all graphs are of class one. That is, in the Erdős–Rényi model of random graphs, in which all n -vertex graphs are equally likely, let p (n) be the probability that an n -vertex graph drawn from this distribution is of class one; then p (n) approaches one in the limit as n goes to infinity. For more precise bounds on the rate at which p (n) converges to one, see Frieze et al. (1988).