1
$\begingroup$

This question already has an answer here:

I know in a graph with n vertices, there are m = (n(n-1)/2) edges, but in a graph with m edges, how many vertices are there?

$\endgroup$

marked as duplicate by Parcly Taxel, Claude Leibovici, user26857, E. Joseph, Shailesh Oct 30 '16 at 9:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your school teaches graph theory before quadratic equations? $\endgroup$ – bof Oct 30 '16 at 2:56
  • $\begingroup$ As @bof implies, just use that equation for m in terms of n and solve for n. That means solving a quadratic equation. At least, if you mean a complete graph in your question, which you did not quite say. $\endgroup$ – Rory Daulton Oct 30 '16 at 10:46
  • $\begingroup$ @bof I didn't know what to tag it, I $\endgroup$ – alecr Oct 30 '16 at 16:46
2
$\begingroup$

It's not clear in your question if you are assuming that $G$ is a complete graph. In order to answer this accurately, we need to know something more about the graph that contains the $m$ edges.

For example:

  • A perfect matching with $m$ edges has exactly $2m$ vertices.
  • A tree with $m$ edges has exactly $m+1$ vertices.
  • A complete graph with $m$ edges will have $\dfrac{1+\sqrt{1+8m}}{2}$ vertices.

Generally speaking as the connectivity of $G$ increases for a fixed number of edges, the number of vertices necessarily decreases.

$\endgroup$

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