in Graph Theory retagged by
13,421 views
41 votes
41 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
13.4k views

9 Answers

70 votes
70 votes
Best answer
Let $m$ be minimum degree and $M$ be maximum degree of a graph, then $\color{navy}{m \le \frac{2E}{V} \le M}$

$m = 3, E = 25, V = ...?$

So, $3 \le \frac{2*25}{V}$

$V\le \frac{50}{3}$

$V \le 16.667 \color{maroon}{\Rightarrow V = 16}$
edited by

4 Comments

Thank you @ASNR1010! :)

2
2

G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at most 3. Then the minimum possible value of n is ?

If question like this then below is answer.

Let, Max degree M=3

2e/n <= M

2(25)/n <= 3

50/3 <= n

16.6666 <= n

Here n can not be 16 or less.

So, n>=17.

So, minimum n possible is 17.

1
1

@rajankakaniya I didn’t get the concept of ceil and floor here, Can you please explain it a bit  more?

0
0
10 votes
10 votes
k.V<=2E

so,3V<=2*25=$\left \lfloor 50/3 \right \rfloor =16$

Ans:16
8 votes
8 votes
According to Handshaking Lemma: The Sum of degree of all the vertices is equal to the twice the number of edges.

in our question:

Number of vertices = n

Number of edges = 25

3 * n = 2  * 25

3n=50

n=16.667

n =16 which is the maximum possible value
reshown by
3 votes
3 votes
2*e>=n*k

2*25>=n*3

n<=16.666

so ,n=16
Answer:

Related questions