1
$\begingroup$

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$
  • $\begingroup$ Related question: What are all the possible numbers of vertices if it is guaranteed that any simple graph on $N$ edges is connected? $\endgroup$ – Batominovski Jun 27 '16 at 23:37
2
$\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$

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.