# sparse graph

(definition)

**Definition:**
A *graph* in which the number of *edges* is much less than the possible number of edges.

**Generalization** (I am a kind of ...)

*graph*.

**See also**
*dense graph*, *complete graph*, *adjacency-list representation*.

*Note:
A **directed graph* can have at most n(n-1) edges, where n is the number of *vertices*. An *undirected graph* can have at most n(n-1)/2 edges.

*
** There is no strict distinction between sparse and dense graphs. Typically, a sparse (connected) graph has about as many edges as vertices, and a dense graph has nearly the maximum number of edges.*

Author: PEB

## More information

*Dense_graph [Wikipedia]*

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 2 December 2019.

HTML page formatted Mon Dec 2 09:10:23 2019.

Cite this as:

Paul E. Black, "sparse graph", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 2 December 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/sparsegraph.html