Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
1  
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
1  
And $n\choose2$ $\geq$ $500$ will give you $n \geq 32$ –  Kirthi Raman May 14 '12 at 16:55
1  
It should be $n \geq 33$ not $32$ –  Kirthi Raman May 14 '12 at 17:03
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.