Describe the minimum number of vertices in a simple graph (no loops or multiple edges) with $e$ edges.
I can't derive a formula for this, I don't even know if this is possible.
Anyway, it's not hard to see that the complete graph is the one that optimizes the use of vertices, for example the minimum for $e=3$ is the number of vertices en $K_3$, the minimum for $e=6$ is the number of vertices in $K_4$, the minimum for $e=10$ is the number of vertices in $K_5$ and so on…so I would know this:
If $2 \leq e \leq 3$ the minimum is $3$
If $4 \leq e \leq 6$ the minimum is $4$
If $7 \leq e \leq 10$ the minimum is $5$ and so on…
But I can't see how to derive a formula…is that possible? If so, how?
Best Answer
The maximum number of edges in an $n$-vertex simple graph is $\binom n2=\frac{n(n-1)}2=T_{n-1}$ where $T_n$ denotes the $n$th triangular number. It is possible to find $n$ given $T_n$ using what is known as a triangular root: $$n=\frac{\sqrt{8T_n+1}-1}2$$ Hence the smallest number of vertices that will support a graph with $e$ edges is $$\left\lceil\frac{\sqrt{8e+1}-1}2+1\right\rceil$$ which can be simplified to $$\left\lceil\sqrt{2e}+\frac12\right\rceil$$ $\lceil x\rceil$ denotes the ceiling function, the smallest integer greater than or equal to $x$.