Graph Theory Q2 (basic)

Let $G = (V,E)$ be the graph. Let $d(x)$ be the degree function defined on $V$ . Note the identity $\sum_{x \in V} d(x) = 2*|E|$ , as each edge in $E$ contributes to the degree functions of each of its two vertices.

We are told the maximum value of $d(x)$ is at most $5$ . Thus $2*|E| = 42 = \sum_{x \in V} d(x) \leq 5*|V| = 5 n$ . This simplifies to $\frac{42}{5} \leq n$ . Since n is an integer, $n \geq 9$ .

It is not difficult to fit $21$ edges into a graph with $9$ vertices while respecting the upper bound on $d(x)$ .