0
$\begingroup$

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.

  • 2
    It should be $n \geq 33$ not $32$2012-05-14

1 Answers 1

5

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$

And there you go.