# Vertices required to construct a graph with at least $500$ edges

On our practice exam, our teacher gave us this problem and this solution:

What is the fewest number of vertices required to construct a complete graph with at least $500$ edges? (Show your work but do not attempt to simplify your answer too much!)

Answer: We need to select $n$ such that $\dbinom{n}{2} \geq 500$.

I do not understand how she got to this answer. I tried to start with the definition of a complete graph, but where to go from there, I had no idea.

-
A complete graph is simply a set of $n$ vertices and every possible edge between them, i.e. choose any two vertices ($n$ choose $2$) and there should be an aedge between them. – Keivan May 14 '12 at 16:44
If there are $n$ vertices, pick a vertex and see how many vertices can be connected to that ? $n-1$? Each of the $n$ vertices are connected to $n-1$ in $n(n-1)$ ways, but you are counting each connection twice, therefore total connections should be $\frac{n(n-1)}{2}$ which is $n\choose2$ – Kirthi Raman May 14 '12 at 16:54
And $n\choose2$ $\geq$ $500$ will give you $n \geq 32$ – Kirthi Raman May 14 '12 at 16:55
It should be $n \geq 33$ not $32$ – Kirthi Raman May 14 '12 at 17:03

## 1 Answer

The complete graph with $n$ vertices has $\dbinom{n}{2}$ edges. So, we have:

$$\dbinom{n}{2} \geq 500$$

$$\frac{n(n-1)}{2} \geq 500$$

$$n^2-n-1000 \geq 0$$

-