# (Graph) - How to find number of vertices given number of edges and some information on the degrees of vertices?

Graph G has 21 edges, 3 vertices which have a degree of 4, other vertices have a degree of 3. How many vertices are there in total?

• Do you know about the handshaking lemma? Jan 31, 2017 at 6:01

We know that the sum of degree across all nodes is equal to twice the number of edges (Handshaking Lemma). Let there be $N$ vertices in this graph.
We have \begin{align} 3 \cdot 4 + 3 \cdot (N-3) &= 2 \cdot 21 \\ 12 + 3 \cdot (N-3)&= 42\\ 3 \cdot (N-3)&= 30 \\ (N-3) &= 10\\ N &= 13\\ \end{align}