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?
$\endgroup$ 11 Answer
$\begingroup$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.
$\endgroup$
