Test Book Test

Question

An Undirected graph G with only one simple path between each pair of vertices has two vertices of degree 4, one vertex of degree 3 and two vertices of degree 2. Number of vertices of degree 1 are _____________ ?

Answer 1

In the question, it is given that: 

An Undirected graph G with only one simple path between each pair of vertices

 This implies that the graph is a tree.

Now,

• 2 vertices have degree 4.
• 1 vertex has degree 3.
• 2 vertices have degree 2.

Let number of vertices of degree 1 be x.

According to Handshaking Lemma,

$\sum_{v\epsilon V}^{}$deg(v) = 2|E|

So, (2*4) + (1*3) + (2*2) + (x*1) = 2[(2+1+2+x)-1] {The graph is a tree, so for 'n' vertices, we have 'n-1' edges}

Solving, we get x=7.

So, 7 vertices have degree 1.