GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
88 views

Let G be a graph with 10 vertices and 31 edges. If G has 3 vertices of degree 10, 1 vertex of degree 8 and 2 vertices of degree 5 and the other four vertices of degree at least 3, how many vertices are of degree 3________?

my solution:

Σ deg(v) = 2|E|

3*10 + 1*8 + 2*5 + 4*(>=3) = 2*31

4*(>=3) = 62- (30+8+10) = 14

I think we can have 3 vertices each of degree 3 and vertex of degree 5, so my answer is 3 but given answer is 2.

Given answer: 2

asked in Graph Theory by Veteran (14.4k points)   | 88 views
3 vertex of degree 10 means it is a multigraph...in simple graph degree cannot be greater than 9...or this que may be framed wrongly
multigraph also follows this property:
Σ deg(v) = 2|E|

 

what's wrong?

1 Answer

+4 votes
Best answer
ohk,

sum of degree  = 2 * edges

3 * 10 +  1 * 8 + 2 * 5  + x1 + x2 + x3  + x4 =  2 * 31

x1 + x2 + x3 + x4 =   62 - 48

x1 + x2 + x3 + x4 = 14

each node have degree atleast three means  

x1 + x2 + x3 + x4 =   14 - 4 * 3 = 2

x1 + x2 + x3 + x4 = 2         

Means either one node take 2 value , means  one node have degree 3 + 2 :  5 ( Not possible , because their are only 2 nodes of degree 5 )

Or  

two nodes have 1 , 1 value       means two nodes have 4 degree , and left two nodes have 3 degree.

Hence nodes having degree  = 3  are 2.
answered by Loyal (2.7k points)  
selected by
( Not possible , because their are only 2 nodes of degree 5 )  i was thinking the same later because it is mentioned in the question that there 2 vertices of 5 degree.
thanks!

You can also do it like this:

Let 'x' be the vertices of degree 3

So, (4-x) vertices are of degree >=4 (because 4 vertices have degree >=3)

 

So,

3(10) + 1(8) + 2(5) + x(3)  + (4-x)(4) >= 62

$\therefore$  2 >= x

Yes, thats why  I have taken >= 62
Top Users Feb 2017
  1. Arjun

    5288 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1690 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,860 questions
26,010 answers
59,673 comments
22,113 users