Dense and sparse graphs — [Notes]

· If a directed graph has |V| vertices, how many edges can it have?
· Maximum Number of Edges
· The Density of a Graph
· Sparse Versus Dense Graphs

If a directed graph has |V| vertices, how many edges can it have?

• The first vertex can have an edge to every vertex (including itself): |V| edges
• The second vertex can have an edge to every vertex (including itself): |V| edges
• … and so on for each of the |V| vertices; and all these edges are distinct
• So, the maximum total number of edges possible is |E| = |V|x|V| = |V|²
• A graph with “close to” |V|² edges is considered dense
• A graph with “closer to” |V| edges is considered sparse

Maximum Number of Edges

https://www.baeldung.com/cs/graphs-sparse-vs-dense

The Density of a Graph

Sparse Versus Dense Graphs