2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It seems relevant that each edge connects two vertices, and that $\binom{3}{2} = 3$, $\binom{4}{2} = 6$, $\binom{5}{2} = 10$. $\endgroup$ – Matthew Leingang Oct 4 '16 at 22:13
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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