Finding the number of vertices in a complete graph without finding the roots of a quadratic I'm taking a class where we are often asked to answer questions like the following:

If G is a complete graph with 105 edges, how many vertices does G have?

If I were to solve this question, I would do the following:
$
\begin{align}
\left| E(G) \right| &= 105 \\
\sum_{v \in V(G)} deg(v) &= 2 \left| E(G) \right| \\
\left| V(G) \right| \cdot 104 &= 2 \cdot 105 \\
\left| V(G) \right| &= \frac{2 \cdot 105}{104} \\
\end{align}
$
Or, more generally:
$
\begin{align}
\left| V(G) \right| &= x \\
\left| E(G) \right| &= x - 1 \\
\sum_{v \in V(G)} deg(v) &= 2 \left| E(G) \right| \\
x \left( x - 1 \right) &= 2 \left| E(G) \right| \\
\end{align}
$
Which is clearly a quadratic.
Here's the issue--we aren't allowed calculators on the test, are short on time, and can have questions involving upwards of 1,000 edges. That is, solving by long division or finding the roots of a quadratic takes way too much time manually on the test.
Is there a faster, easier, non-mechanically assisted way of solving this sort of question?
 A: In this particular case (number of edges in a complete graph), it's easy, because the number is $\frac12 n(n-1)$. So you have
$$n(n-1)=210$$
and $n(n-1)$ lies between the consecutive squares $(n-1)^2$ and $n^2$. So obviously $n=15$. You can use this trick well into the thousands, I would think.
A: You could use guess and check. If a complete graph has $n$ vertices, then it has $f(n) = n(n-1)/2$ edges --- the number of different "handshakes" between $n-1$ people if everyone shakes everyone else's hand.
So for example, you could compute various values of $f(n)$: $f(1) = 1$, $f(2) = 3$, $f(3) = 6$, $f(4) = 10$, and so on. You can guess large values for $n$ and small values for $n$. The essential property that makes this process easy is that the function $f$ is increasing — if you guess a number of nodes $a$, but $f(a)$ is too large, then you know that $a$ itself is too large.
Hence you can use binary search to find the correct answer without doing too many calculations.

Here is an example. You tell me that the number of edges is 105. 

I might guess $a=4$, so $f(a) = 4\cdot 3 / 2 = 12$— too small. 
I guess $a=10$ so $f(a) = 10\cdot 9 / 2 $ = 45— too small. 
I guess $a=20$ so $f(a) = 20\cdot 19/2 = 190$— too large.
I guess $a=15$ so $f(a) = 15\cdot 14/2 = 105$. Bingo! $n=15$.
These calculations can be performed almost instantaneously in your head especially if you pick convenient values to guess. And you sometimes begin to memorize various values of $f$, so you have a feel for how large a good guess is.
A: If you can estimate square roots, you can try the following approach:  If there are $v$ vertices and $e$ edges in a complete graph, then we have $e=\frac{v(v-1)}{2}$.  So $2e=v^2-v$.
But also $v^2-v$ is between $(v-1)^2$ and $v^2$.  That is, $(v-1)^2<2e<v^2$.  
So $v-1<\sqrt{2e}<v$.  So $v$ can be found by taking the square root of $2e$ and rounding up to the next higher integer.
In your example of $105$ edges, you would note that $\sqrt{210}=14\large\bf{.}\ldots$ , and so the number of vertices is $15$.
A: The number of edges of $K_n$ is $\binom{n}2=\frac12n(n-1)$, so if you’re told that you have $e$ edges, you need to solve $2e=n(n-1)$ for $n$. It’s always true that $n-1<\sqrt{n(n-1)}<n$, so
$$n=\left\lceil\sqrt{2e}\right\rceil\;,$$
the integer obtained by rounding up $\sqrt{2e}$. For values of $2e$ with no more than four digits, $n$ will be a two-digit number, and you should be able to pin it down quickly with a combination of mental and pencil-and-paper arithmetic. For instance, with $e=105$ you’re looking at $\sqrt{210}$; since $15^2=225$, $n=15$ looks like a good bet even if you don’t know that $14^2=196$, and a quick calculation verifies that $105=\frac12\cdot14\cdot15=7\cdot15$. 
For larger values of $e$ there’s more work, and knowing a pencil and paper algorithm for extracting square roots would help; for $e<500,000$ you need to extract at most three digits, and that’s a fairly quick calculation. The Babylonian method mentioned there involves only division, but for numbers of this size it’s generally going to be about as cumbersome.
Ultimately you can’t avoid having to extract a square root to within an integer by some method.
