GATE CSE 2017 Set 2 | Question: 23

Question

$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 _________ .

Answer 1

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}$

Comments

Thanks

---

If max degree were given in the question instead of min, then we have to apply ceil?

---

Yes in that case we can apply ceil. But, minimum vertices n will be 17 (not maximum). @neel19

---

@rajankakaniya please elaborate. I didn’t understood your point.

---

@rajankakaniya

Yes in that case we can apply ceil. But, minimum vertices n will be 17 (not maximum).

How can you explain??

---

@ASNR1010 how can we tag people using @ ? Sorry for this silly question but I tried, not working for me.

---

Right click on the user and copy link…

Like yours…

https://gateoverflow.in/user/ankit3009

Now remove the front and add ‘@’ or not

@ankit3009

Now it’s done.🙂

---

Thank you @ASNR1010! :)

---

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.

---

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

Answer 2

k.V<=2E

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

Ans:16

Answer 3

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

Answer 4

2*e>=n*k

2*25>=n*3

n<=16.666

so ,n=16