GATE CSE
First time here? Checkout the FAQ!
x
0 votes
41 views
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 _____________ ?
asked in Graph Theory by Active (2k points)   | 41 views

1 Answer

+5 votes
Best answer

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.

answered by Boss (7.3k points)  
selected by

Related questions

0 votes
0 answers
1
asked ago in Programming by Rock (285 points)   | 35 views
+1 vote
1 answer
3
asked in Digital Logic by S Ram Active (2.2k points)   | 129 views


Top Users Mar 2017
  1. rude

    4768 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2728 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1378 Points

  9. Bikram

    1342 Points

  10. Sanjay Sharma

    1126 Points

Monthly Topper: Rs. 500 gift card

21,517 questions
26,845 answers
61,157 comments
23,181 users