GATE CSE
First time here? Checkout the FAQ!
x
0 votes
45 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 (2.1k points) 3 17 51 | 45 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 Veteran (10.2k points) 6 44 108
selected by

Related questions

0 votes
0 answers
1
asked in Programming by Rock (333 points) 1 7 16 | 82 views
+1 vote
1 answer
3
asked in Digital Logic by S Ram Active (2.5k points) 2 16 48 | 155 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8960 Points

  4. srestha

    6450 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4032 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Notable Question Sedhu Raman
Notable Question cse23
Notable Question vishwa ratna
Notable Question learner_geek
Popular Question Devshree Dubey
Popular Question nish kim
Popular Question Simar sandhu
Popular Question Rashi Gupta
Notable Question Akriti sood
Popular Question Samujjal Das
27,407 questions
35,256 answers
84,506 comments
33,480 users