Max and min amount of nodes in a graph

Question

Suppose you are given an undirected (simple) graph $G = (V,E)$ with $|E| = 30$, and $d(v) \ge 3$ for all $v \in V$. How many nodes can the graph possibly have? Give both an upper and a lower bound.

How would one calculate the solution?

Thank you!

Answer 1

Since $$3|V|=\sum_{v\in V}3\le \sum_{v\in V}\deg v=2|E|\le {|V|(|V|-1)},$$ we have $9\le |V|\le 20$. The lower bound is attained by a complete graph on $9$ vertices with any $6$ edges removed, the upper bound is attained by five disjoint copies of a complete graph on $4$ vertices.