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
    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.2012-05-14
  • 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$2012-05-14
  • 1
    And $n\choose2$ $\geq$ $500$ will give you $n \geq 32$2012-05-14
  • 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.