12,514 views
$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 _________ .

### Subscribe to GO Classes for GATE CSE 2022

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

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

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.

## 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.

The number of odd degree vertices has to be even.

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