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 in Programming by Rock (305 points)   | 55 views
+1 vote
1 answer
3
asked in Digital Logic by S Ram Active (2.3k points)   | 134 views


Top Users Apr 2017
  1. akash.dinkar12

    3782 Points

  2. Divya Bharti

    2696 Points

  3. Deepthi_ts

    2270 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Sanjay Sharma

    1692 Points

  7. Debashish Deka

    1668 Points

  8. Shubham Sharma 2

    1610 Points

  9. Prashant.

    1580 Points

  10. Arjun

    1570 Points

Monthly Topper: Rs. 500 gift card

22,135 questions
28,125 answers
63,467 comments
24,261 users