0
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .