# Maximal number of vertices in simple undirected graph

I have a simple, undirected graph for which $\;|E|=2|V|+5\;$ and in which every vertex has degree at least $\;5\;$. I'm asked what's the maximal number for $\;V\;$.

Now, this is how I thought: no loops or parallel edges allowed, which means that if the graph has one vertex then it automatically has to have other five, so $\;|E|\ge 6\;$ . But if I add one vertex more then I can connect it with other five of the first six vertices...It really is confusing.

And I read that there can also be non-connected simple graphs, though I'm not sure whether this applies to my case.

Any help will be appreciated.

• You can use: $E \le 3V-6$ – openspace Feb 23 '16 at 21:00
• But it gets you lower bound – openspace Feb 23 '16 at 21:01
• @openspace thank you for the comment. – DonAntonio Feb 23 '16 at 21:06
• not at all , my friend :) – openspace Feb 23 '16 at 21:07

Hint: You surely know that $\sum_{v\in V}\text{deg}(v)=2|E|$. If $\text{deg}(v)\geq 5$ for every $v\in V$ then you have $2|E| = \sum_{v\in V}\text{deg}(v)\geq \sum_{v\in V} 5 = 5|V|$. In other words $2|E| \geq 5|V|$. You also know that $|E|=2|V|+5$. Substitute that into the inequality and solve for $... \geq |V|$ and you will be done.