Hi I am trying to figure out the following problem. A simple connected graph G = (V, E) with |E| = 15 , has three vertices of degree 4, two of degree 1 and the remaining vertices have degree 2. How many vertices does G have?
So I know by handshaking lemma the sum of vertices must be twice the amount of edges so in this case :
3×4 + 2×1 = 14.
|E| = 15 therefore the sum of vertices must be 30. 30-14 = 16. Meaning that the number of vertices of degree 2 is 8.
Is this answer correct ?
Thanks
Best Answer
$2|E| = \sum_{v \in V} d_G(v)$.
As there are 3 vertices of degree 4, 2 vertices of degree 1, and $n$ vertices (for some $n$) of degree 2, and $|E|=15$ plugging this into the above gives
$2 \times 15 = 3 \times 4 + 2 \times 1 + 2 \times n.$
Solving for $n$ gives $n=8$ so there are 8 vertices of degree 2.
ETA: Saw the rest of your post. YES your answer and reasoning is correct.