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.

  • 1
    $\begingroup$ You can use: $E \le 3V-6$ $\endgroup$ – openspace Feb 23 '16 at 21:00
  • $\begingroup$ But it gets you lower bound $\endgroup$ – openspace Feb 23 '16 at 21:01
  • 1
    $\begingroup$ @openspace thank you for the comment. $\endgroup$ – DonAntonio Feb 23 '16 at 21:06
  • $\begingroup$ not at all , my friend :) $\endgroup$ – 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.

  • $\begingroup$ Oh, of course! I am way too embedded into pure mathematics now...thank you very much indeed. $\endgroup$ – DonAntonio Feb 23 '16 at 21:04

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.