If I already know edges how can I get the maximum number of vertices?

Question: There is a graph that has $36$ edges, and where every vertex has degree at least $5$. What is the maximum number of vertices this graph could have?

I think the sum of degrees is $36\cdot 2$ which is $72$. And the sum of degrees is bigger or equal than adding the least degree of every vertices together.

Therefore, $72\geq 5n$ and then $14.4\geq n$, so the maximum number of vertices is $14$. Is it correct?


You did half of the job. You must show that there exists a graph on $n=14$ vertices with $36$ edges such that the minimum degree is $5$. I propose the following.

Let $G$ be a graph on $14$ vertices with two (vertex-induced) subgraphs $G_1$ and $G_2$. The subgraph $G_1$ is isomorphic to the complete graph $K_6$ (this it has already taken $\displaystyle \binom{6}{2}=15$ edges). The subgraph $G_2$ has $8$ vertices $v_1,v_2,\ldots,v_8$. For each $i\in\{1,2,\ldots,8\}$, join $v_i$ with $v_{i-2}$, $v_{i-1}$, $v_{i+1}$, $v_{i+2}$, and $v_{i+4}$ (indices are calculated modulo $8$). Thus, $G_2$ has $\dfrac{1}{2}\cdot 8\cdot 5=20$ edges. We now need one last edge. Just pick one vertex of $G_1$ and one vertex of $G_2$, then join them with an edge.

  • $\begingroup$ Perfect! So 14 is the correct answer for this question? $\endgroup$ – An Yan Oct 18 '18 at 8:15
  • 1
    $\begingroup$ Yes, the answer is $14$. $\endgroup$ – Batominovski Oct 18 '18 at 9:08
  • $\begingroup$ Great! Thank you very much $\endgroup$ – An Yan Oct 18 '18 at 9:19

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.