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

You must log in to answer this question.

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