0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Do you know about the handshaking lemma? $\endgroup$ Jan 31, 2017 at 6:01

1 Answer 1

1
$\begingroup$

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} $$

$\endgroup$
1
  • $\begingroup$ Thank you! I wasn't sure if I could do that so I feel stupid for asking this question. Cheers $\endgroup$
    – bashbin
    Jan 31, 2017 at 6:05

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.