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

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.
• Yes, the answer is $14$. – Batominovski Oct 18 '18 at 9:08