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

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?

---

@tusharb  

Given real numbers x and y, integers m and n and the set of integers 𝑍 floor and ceiling may be defined by the equations

⌊𝑥⌋=max{𝑚∈𝑍∣𝑚≤𝑥},

⌈𝑥⌉=min{𝑛∈𝑍∣𝑛≥𝑥}.

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