in Graph Theory retagged by
12,514 views
39 votes
39 votes
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
in Graph Theory retagged by
by
12.5k views

Subscribe to GO Classes for GATE CSE 2022

9 Answers

0 votes
0 votes

Since ,Degree of Vertices is 25.

And It is also given that each vertex have at least three 3 degree .

On the basis of above ,We can conclude that

Minimum degree δ(u)=3

And We Know that by basic Graph theory theorem that

δ(u) .|V|<= 2*|E|

3 * |V| <=2 *25

|V|=Floor(50/3)

|V|=16

0 votes
0 votes

In a simple graph

Sum of degree of all the vertices = 2 * number of edges

Given edges = 25, each vertex degree = 3

no of vertices * 3 = 2*25

Finally number of vertices = floor [16.6] = 16

0 votes
0 votes
no of vertices =n

min degree for each vertex =3

now total degree =3*n

no of edge =25

now we know for undirected graph ,

2*edge = sum of degree

sum of degree =2*25 =50

now 3*n = 50

  n= 16.67

 now if someone confused which one to took ceil of floor

now just think if we put n= 17 then 3*17 =51 which is not the sum of degree as it is 50 and we can’t say 16 vertex of degree 3 and one vertex of degree 2 as min degree should be 3.

now if you choose 16 then 16*3 =48 which is also not equal to 50 also but here is the possibility that we have 15 vertex of degree 3 and one vertex of degree 5 as 5 is greater than min degree 3 .so ,3*15 +5 =50 .

thats why we took 16 as answer.
–3 votes
–3 votes

Ans : 17

Sum of Degrees of Vertices Theorem

If G = (V, E) be a non-directed graph with vertices V = {V1, V2,…Vn} then

n∑i=1 deg(Vi) = 2|E|

If the answer is 16 i.e. 16 Vertices of which degree of each vertex is 3 then Sum of degree of all the vertices is 48 but according to Sum of degree of Vertices therom it should be 2*25= 50. Hence, the answer should be 17.

2 Comments

The number of odd degree vertices has to be even.
4
4

Minimum degree is 3 . so if you do 16*3 = 48 then remaining are two which cannot be covered by any vertex. So we do 15*3 = 45 and last vertex has degree 5. So maximum is 16

3
3
Answer:

Related questions

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