How can I get maximum number of vertices if I already know edges

Question

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?

Answer 1

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.