Density (graph theory)

from Wikipedia, the free encyclopedia

The density or edge density of a simple graph is graph theory , a ratio that reflects the ratio of actual existing edges indicating compared to potentially possible connections. The density can assume values ​​between 1 ( complete graph ) and 0 (graph without edges).


Be a simple graph. Then is called

the density or edge density of the graph. The density is the ratio of the number of edges of the graph to the number of edges of the complete graph with the same number of nodes. There is also the definition to get clearer results for asymptotic statements for .


The density of a graph plays a role in extremal graph theory . One of the questions in this area is what density of a graph is necessary to guarantee the existence of a certain sub-graph.