# Find number of vertices when given number of edges

A Simple Connected Graph G has $M$ vertices and 4 edges, find $M$

Now lets say we didn't have any more info than what's mentioned above. By drawing out a couple of graphs I know that $M$ could possibly be $4$ or $5$. But when working with more than $4$ edges it can become a little difficult drawing the graphs out.

Is there any formula/algorithm that can help to quickly find the number of vertices in a simple connected graph when given the number of edges?

I am specifically talking about the number of edges which can't be made equal to $\frac{n(n-1)}{2}$ and then solved for $n$. E.g. $4$.

Doing so with $4$ gives:

$$n-\frac{1\pm\sqrt{33}}{2}$$

But with 10 edges on the other hand it works.

So for 4 edges, is there any formula/algorithm that would give me the number of vertices?

• Related question: What are all the possible numbers of vertices if it is guaranteed that any simple graph on $N$ edges is connected? – Batominovski Jun 27 '16 at 23:37

Any connected graph with $n$ vertices must have at least $n-1$ edges to connect the vertices. Therefore, $M=4$ or $M=5$ because for $M \geq 6$ we need at least 5 edges.
Now, let's say we have $N$ edges. For $n$ vertices, there needs to be at least $n-1$ edges and, as you said, there are most $\frac{n(n-1)}{2}$ edges, so we need to solve the following inequality for $n$: $$n-1 \le N \le \frac{n(n-1)}{2}$$ This is our "algorithm" for solving for possible $n$ verticies in terms of $N$ edges.