GATE CSE
First time here? Checkout the FAQ!
x
0 votes
44 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)   | 44 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 (8.1k points)  
selected by

Related questions

0 votes
0 answers
1
asked in Programming by Rock (315 points)   | 73 views
+1 vote
1 answer
3
asked in Digital Logic by S Ram Active (2.4k points)   | 146 views


Top Users Aug 2017
  1. Bikram

    4990 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3286 Points

  5. rahul sharma 5

    3162 Points

  6. makhdoom ghaya

    2510 Points

  7. just_bhavana

    2398 Points

  8. stblue

    2144 Points

  9. Tesla!

    2066 Points

  10. joshi_nitish

    1796 Points


25,022 questions
32,159 answers
74,902 comments
30,202 users