Informally, a graph with relatively few edges is *sparse*,
and a graph with many edges is *dense*.
The following definition defines precisely what we mean
when we say that a graph ``has relatively few edges'':

Definition (Sparse Graph)Asparse graphis a graph in which .

For example, consider a graph with *n* nodes.
Suppose that the out-degree of each vertex in *G* is
some fixed constant *k*.
Graph *G* is a *sparse graph* because
.

A graph that is not sparse is said to be *dense*:

Definition (Dense Graph)Adense graphis a graph in which .

For example, consider a graph with *n* nodes.
Suppose that the out-degree of each vertex in *G* is
some fraction *f* of *n*, .
E.g., if *n*=16 and *f*=0.25,
the out-degree of each node is 4.
Graph *G* is a *dense graph* because
.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.