Suppose a simple graph G has 8 vertices. What is the maximum number of
edges that the graph G can have?
The formula for this I believe is
n(n-1) / 2
where n = number of vertices.
8(8-1) / 2 = 28. Therefore a simple graph with 8 vertices can have a maximum of 28 edges. Is this correct?
Best Answer
Yes, it is. The maximum number of edges is simply the number of pairs of distinct vertices; if there are $n$ vertices, this is
$$\binom{n}2=\frac{n!}{2!(n-2)!}=\frac{n(n-1)}2\;.$$