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$
1
  • $\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$ Oct 4, 2016 at 22:13

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .