3
$\begingroup$

enter image description here

$D=\frac{2|E|}{|V|(|V|-1)}$

Where do the numerator and denominator come from in the definition of graph density ?

1 Answers 1

5

Number of edges in graph $G= |E|$

Maximum no. of edges a graph can have with number of vertices $|V|$ is ${|V|\choose 2}=\frac{|V|(|V|-1)}{2}$

Thus graph density= $\frac{|E|}{\frac{|V|(|V|-1)}{2}}=\frac{2|E|}{|V|(|V|-1)}$