in Graph Theory retagged by
17,243 views
44 votes
44 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
17.2k 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

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