retagged by
17,294 views

9 Answers

2 votes
2 votes
Sum of degree of all vertices < = 2 * no. of edges . [According to Handshaking Lemma]

Let n be number of vertices in graph.
==> 3*n  <= 2*25
==> Maximum value of n = 16
2 votes
2 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.
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

Answer:

Related questions

0 votes
0 votes
0 answers
1
admin asked Mar 30, 2020
1,166 views
Which of the following statements is/are TRUE for an undirected graph?Number of odd degree vertices is evenSum of degrees of all vertices is evenP onlyQ onlyBoth P and QN...
0 votes
0 votes
1 answer
3
admin asked Apr 1, 2020
559 views
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$$n+d$$nd$$nd/2$